leetcode解题: Minimum Moves to Equal Array Elements (453)

发表于 | 分类于

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]

解法1：O(N)

本题巧妙的办法是要想到等价的操作，将n-1个元素都+1等价于将1个元素-1，在选择+1的时候我们都是避开最大的元素，那么-1的时候就要选择最大的元素。那么问题就转化为了将元素全部转化为最小元素，需要多少步，每步减少一个元素的值。
C++

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int minMoves(vector<int>& nums) {
        int minNum = INT_MAX;
        int count = 0;
        for (num : nums) minNum = min(minNum, num);
        for (num: nums) count += (num - minNum);
        return count;        
    }
};

Java

1