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:

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]

分析

这道题可以这样来考虑：从一个数组中选中一个数，除这个数之外的其他数自增1，最后要使这些数字的值都相等，要使步骤最小的话，我们肯定不会选择最小的数，因为增加其他的数字会使得其他数与最小数差距越来越大，步骤反而会增加。这个过程其实是对于每个数字都一样，都是为了增加最小的数，使其与自身相等，而这个步骤的次数就是自身与最小值的差，将所有的差都详解即为总的步骤。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minMoves(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int min = nums[0];
        for (int n: nums) {
            min = Math.min(min, n);
        }
        int result = 0;
        for (int n: nums) {
            result += (n - min);
        }
        return result;
    }
}

相关问题

题目来源