最小操作次数使数组元素相等【力扣LeetCode 每日一题】-北京尧图网络

453. 最小操作次数使数组元素相等网页链接力扣LeetCode力扣LeetCode 每日一题完成每日打卡即可获得力扣积分。获得相应数量的积分能在【力扣商店】换取相应奖品助力每日有题做丰盈积分日益多题目描述给你一个长度为n的整数数组每次操作将会使n - 1个元素增加1。返回让数组所有元素相等的最小操作次数。输入描述一个长度为n的整数数组nums。输出描述返回让数组所有元素相等的最小操作次数。示例示例 1输入nums [1,2,3]输出3解释只需要3 33次操作注意每次操作会增加两个元素的值[1,2,3] [2,3,3] [3,4,3] [4,4,4]示例 2输入nums [1,1,1]输出0数据范围n nums.length1 ≤ nums.length ≤ 10 5 1 \le \text{nums.length} \le 10^51≤nums.length≤105− 10 9 ≤ nums [ i ] ≤ 10 9 -10^9 \le \text{nums}[i] \le 10^9−109≤nums[i]≤109答案保证符合32-bit整数解题思路本题是操作等价转化相对差值求和问题。每次操作会把n - 1个元素同时加1直接模拟操作次数会很多也不方便。关键在于把“增加大多数元素”转化为“减少单个元素”。1. 操作等价转化每次操作选择n - 1个元素加1等价于所有元素都加1再让未被选中的那个元素减1。由于“所有元素同时加1”不会改变任意两个元素之间的相对差值也不会影响最终它们是否相等因此可以忽略这个整体加1的部分。于是原操作等价于每次选择数组中的一个元素将其减1。目标仍然是让所有元素相等。2. 最终相等值只能是最小值如果每次只能把某个元素减1那么元素只能变小不能变大。因此最终所有元素相等时目标值不能大于数组中的最小值否则原本的最小值无法通过“减1”达到更大的值。所以最终相等值必然就是数组的最小值m min ⁡ ( n u m s ) m \min(nums)mmin(nums)3. 计算最少操作次数对于任意元素nums[i]要把它降到最小值m需要的操作次数为n u m s [ i ] − m nums[i] - mnums[i]−m每个元素都必须至少降到m且降到m后不能再继续减小否则会小于目标值。因此总操作次数为∑ i 0 n − 1 ( n u m s [ i ] − m ) \sum_{i0}^{n-1} \bigl(nums[i] - m\bigr)i0∑n−1(nums[i]−m)这正是代码中intm*min_element(a.begin(),a.end());intr0;for(intx:a){rx-m;}returnr;所计算的内容。4. 示例验证对于nums [1,2,3]最小值为1答案为( 1 − 1 ) ( 2 − 1 ) ( 3 − 1 ) 0 1 2 3 (1-1)(2-1)(3-1)0123(1−1)(2−1)(3−1)0123与示例输出一致。对于nums [1,1,1]最小值为1答案为0 0 0 0 00000000也与示例一致。5. 复杂度分析求最小值O ( n ) O(n)O(n)遍历数组累加差值O ( n ) O(n)O(n)总时间复杂度为O ( n ) O(n)O(n)只使用常数个额外变量空间复杂度为O ( 1 ) O(1)O(1)。总结每次让n - 1个元素加1等价于让一个元素减1。由于元素只能减小最终所有元素只能变成数组的最小值。因此最少操作次数就是所有元素与最小值之差的总和直接一次遍历累加即可。代码内容classSolution{public:intminMoves(vectorinta){intm*min_element(a.begin(),a.end());intr0;for(intx:a){rx-m;}returnr;}};

最小操作次数使数组元素相等【力扣LeetCode 每日一题】

相关推荐

备份问题：覆盖保存前怎样留一份可回退副本？新手一步步做

一句话就出的AI-PPT为什么好看不好用？

YOLO小目标检测优化技术与工程实践

更多资讯

分布式ID生成器CosID原理与ShardingSphere集成实践

智能Web IDE架构设计与AI编码实践

跑腿经济崛起：商业模式、技术趋势与实操指南

软件模拟IIC驱动ADXL345三轴加速度计与计步算法实现

高校水电表缴费系统设计与微服务架构实践

Redis核心命令详解与性能优化实践

今日更新

淘宝商品详情API开发实战与性能优化指南

Unity Package Manager刷新错误排查与解决方案

Java record 规范构造器能否被反序列化或反射绕过

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？