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 - 1
个数增加1
,那么实际就是让选定的那一个数减少1
了,比如上例中的[1, 2, 3]
=> [1, 1, 3]
=> [1, 1, 2]
=> [1, 1, 1]
。既然想要知道让数组元素全部相等的最小移动次数,那么就是所有元素与最小元素的差的和了。
Python
class Solution(object):
def minMoves(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return sum(nums) - min(nums) * len(nums)
Java
public class Solution {
public int minMoves(int[] nums) {
int sum = 0;
int min = Integer.MAX_VALUE;
for (int num : nums) {
sum += num;
if (num < min) {
min = num;
}
}
return sum - min * nums.length;
}
}
C++
class Solution {
public:
int minMoves(vector<int> &nums) {
int sum = 0;
int min = INT32_MAX;
for (int num : nums) {
sum += num;
if (num < min) {
min = num;
}
}
return sum - min * nums.size();
}
};