LeetCode453 Minimum Moves to Equal Array Elements

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

样例

1
2
3
4
5
6
7
8
9
10
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,问至少要操作多少次可以让数组中每个数都相等。

(这是easy分类的题目,但是感觉身体被掏空,写了几次都WA了…

其实这题从反面来看比较好考虑,每次让$n-1$个数加1,其实等价于让一个数减1。所以问题就等价于每次让一个数减1,问要经过多少次后能让所有数相等。答案即为$sum - n * minMum$。(也就是所有数都减到最小的那个数为止)

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int minMoves(vector<int>& nums) {
long long sum = 0;
int minNum = INT_MAX;
for (int& x: nums) {
sum += x;
minNum = min(minNum, x);
}
return sum - nums.size() * minNum;
}
};
分享到 评论