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]

Solution:

思路:
Adding 1 to n - 1 elements is the same as subtracting 1 from one element, w.r.t goal of making the elements in the array equal.
So, best way to do this is make all the elements in the array equal to the min element.
sum(array) - n * minimum

Time Complexity: O(N) Space Complexity: O(N)

Solution Code:

public 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 res = 0;
        for (int n : nums) res += n - min;
        return res;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,827评论 0 23
  • 新的一年开始了! 有放鞭炮看焰火的,有开飞机、坐飞机看日出、拍日出的,有励志的,有祝福的,我们却是一家三口睡到日上...
    考槃在涧独寐寤言阅读 208评论 0 1
  • 守口如瓶 病从口入,祸从口出。讲话可是一门大学问,能讲的讲,不能讲的,话哪怕是到了嘴边也要给我咽回去了。我就是急性...
    止戈魏阅读 304评论 0 1
  • 今天店里忙了一整天,答应女儿下午放学去接她也没有兑现。晚上回到家,晚饭也不想吃,一头倒在床上,就想美美补个觉,...
    崔嘉诺阅读 260评论 0 0