[LeetCode] 453. Minimum Moves to Equal Array Elements 最少移动次数使数组元素相等
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.
Example:
Input: [1,2,3] Output: 3 Explanation: Only three moves are needed (remember each move increments two elements): [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
这道题给了我们一个长度为n的数组,说是每次可以对 n-1 个数字同时加1,问最少需要多少次这样的操作才能让数组中所有的数字相等。那么想,为了快速的缩小差距,该选择哪些数字加1呢,不难看出每次需要给除了数组最大值的所有数字加1,这样能快速的到达平衡状态。但是这道题如果老老实实的每次找出最大值,然后给其他数字加1,再判断是否平衡,思路是正确,但是 OJ 不答应。正确的解法相当的巧妙,需要换一个角度来看问题,其实给 n-1 个数字加1,效果等同于给那个未被选中的数字减1,比如数组 [1,2,3],给除去最大值的其他数字加1,变为 [2,3,3],全体减1,并不影响数字间相对差异,变为 [1,2,2],这个结果其实就是原始数组的最大值3自减1,那么问题也可能转化为,将所有数字都减小到最小值,这样难度就大大降低了,只要先找到最小值,然后累加每个数跟最小值之间的差值即可,参见代码如下:
class Solution { public: int minMoves(vector<int>& nums) { int mn = INT_MAX, res = 0; for (int num : nums) mn = min(mn, num); for (int num : nums) res += num - mn; return res; } };
我们也可以求出数组的数字之和 sum,然后用 sum 减去最小值和数组长度的乘积,也能得到答案,注意为了避免整型溢出,将所有变量用长整型 long 来表示,参见代码如下:
解法二:
class Solution { public: int minMoves(vector<int>& nums) { long mn = INT_MAX, sum = 0, res = 0; for (long num : nums) { mn = min(mn, num); sum += num; } return sum - mn * nums.size(); } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/453
参考资料:
https://leetcode.com/problems/minimum-moves-to-equal-array-elements/
https://leetcode.com/problems/minimum-moves-to-equal-array-elements/discuss/93822/Simple-one-liners
相关文章
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- Java实现 LeetCode 689 三个无重叠子数组的最大和(换方向筛选)
- Java实现 LeetCode 689 三个无重叠子数组的最大和(换方向筛选)
- Java实现 LeetCode 462 最少移动次数使数组元素相等 II
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 420 强密码检验器
- Java实现 LeetCode 330 按要求补齐数组
- LeetCode(69):x 的平方根
- LeetCode(4):两个排序数组的中位数
- LeetCode:4_Median of Two Sorted Arrays | 求两个排序数组的中位数 | Hard
- LeetCode(108):将有序数组转换为二叉搜索树
- LeetCode-1814. 统计一个数组中好对子的数目【哈希表】
- LeetCode-1441. 用栈操作构建数组【哈希表,栈,数组,模拟】
- LeetCode-481. 神奇字符串【双指针,字符串】
- LeetCode-427. 建立四叉树【树,数组,分治,矩阵】
- Python 刷Leetcode题库,顺带学英语单词(19)
- Leetcode 81. 搜索旋转排序数组 II
- Leetcode 1551. 使数组中所有元素相等的最小操作数
- Leetcode 80. 删除有序数组中的重复项 II
- [LeetCode] 152. 乘积最大子数组 ☆☆☆(动态规划)
- [LeetCode] 46. Int数组全排列 ☆☆☆(回溯)
- 【Leetcode刷题Python】53. 最大子数组和