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]

链接：https://leetcode.com/problems/minimum-moves-to-equal-array-elements/#/description

3/26/2017

我的答案，错误的！！！

n * x = sum + (n - 1) * y, 其中x是最终每个元素的值，y是move的次数，sum是最初的和

y = (n * x - sum)/(n - 1)，只要y是整数就可以了。

但是是错误的，为什么？有溢出，test case ［1，1，2147483647］

 1 public class Solution {
 2     public int minMoves(int[] nums) {
 3         if (nums.length <= 1) return 0;
 4         int max = Integer.MIN_VALUE;
 5         int diffCount = 0;
 6         int sum = 0;
 7         for (int i = 0; i < nums.length; i++) {
 8             if (nums[i] > max) max = nums[i];
 9             sum += nums[i];
10         }
11         int element = max;
12         while ((element * nums.length - sum) % (nums.length - 1) != 0) element++;
13         return (element * nums.length - sum) / (nums.length - 1);
14     }
15 }

之前是用最大值算的，答案是错的。尝试用最小值算却对了。为什么？

标准答案里面第三种方法有解释，我总结来说：

每次给最小的n-1个元素加上max-min的值，加过之后本来第二大元素成为新的最大值，之前最大元素和之前最小元素都是之前最大元素值。

如此进行，每一步最小值的数目都在上升，至少加1（上一轮最大元素），或者更多（输入时最小值有重复，注意，只能是最小值，之后元素若有重复必然在过程中成为最大值）。而且，输入中的最小值，永远都是数组中的最小值！

最后我们加了多少呢？最小值和每个元素值的差值和。（第一轮是与最大元素差值，第二轮是与输入次大元素差值，直到最后一轮是输入中次小元素差值）。

解法很好写，过程很难想。为什么最大值不行？因为是往上加的过程？

同样的代码还可以用来解释第五种方法，非常巧妙！

每次给n-1个值加1，重复m次数之后的m其实相当于每次给1个值减1，重复m次。

看到第6中解法，才发现用最小值求差的代码就是第六种啊哈哈

 1 public class Solution {
 2     public int minMoves(int[] nums) {
 3         if (nums.length <= 1) return 0;
 4         int min = Integer.MAX_VALUE;
 5         int moveCount = 0;
 6         for (int i = 0; i < nums.length; i++) {
 7             if (nums[i] < min) min = nums[i];
 8         }
 9         for (int i = 0; i < nums.length; i++) {
10             if (nums[i] > min) moveCount += nums[i] - min;
11         }
12         return moveCount;
13     }
14 }

标准答案：

https://leetcode.com/articles/minimum-moves-to-equal-array-elements/