首页 > 其他 > 详细

Leetcode: Minimum Moves to Equal Array Elements

时间:2016-12-08 03:13:26      阅读:233      评论:0      收藏:0      [点我收藏+]
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]

idea 1: suppose it takes y steps to equal each elements, then this equation stands:

(min + y) * num.length == sum + (num.length-1)*y,   where min + y is each element‘s value when all elements equal

idea 2: Add 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

 1 public class Solution {
 2     public int minMoves(int[] nums) {
 3         if (nums==null || nums.length==0) return 0;
 4         int min = Integer.MAX_VALUE;
 5         int sum = 0;
 6         for (int num : nums) {
 7             min = Math.min(min, num);
 8             sum += num;
 9         }
10         return sum - min * nums.length;
11     }
12 }

 

Leetcode: Minimum Moves to Equal Array Elements

原文:http://www.cnblogs.com/EdwardLiu/p/6143420.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!