MinimumMovesToEqualArrayElements2 [source code]

public class MinimumMovesToEqualArrayElements2 {
    public int minMoves(int[] nums) {
        int n = nums.length;
        int maxIndex = 0;
        int min = Integer.MAX_VALUE, max = 0;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < min) min = nums[i];
            else if (nums[i] > max) {
                max = nums[i];
                maxIndex = i;
            }
            sum += nums[i];
        }
        int count = 0;
        while (n * min < sum) {
            sum = 0;
            min = Integer.MAX_VALUE;
            max = 0;                
            for (int i = 0; i < n; i++) if (i != maxIndex) nums[i]++;
            count++;
            for (int i = 0; i < n; i++) {
                if (nums[i] < min) min = nums[i];
                else if (nums[i] > max) {
                    max = nums[i];
                    maxIndex = i;
                }
                sum += nums[i];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        MinimumMovesToEqualArrayElements2 tester = new MinimumMovesToEqualArrayElements2();
        int[] input1 = {1,2,3};//3
        assert tester.minMoves(input1) == 3 : "fail 1";
        int[] input2 = {1,2,3,4};//6
        assert tester.minMoves(input2) == 6 : "fail 2";
        int[] input3 = {3,3,3,1};//6
        assert tester.minMoves(input3) == 6 : "fail 3";
        int[] input4 = {1,2,3,1};//3
        assert tester.minMoves(input4) == 3 : "fail 4";
        int[] input5 = {1,1,3,1};//2
        assert tester.minMoves(input5) == 2 : "fail 5";
        int[] input6 = {1,2147483647};
        System.out.println(tester.minMoves(input3));
    }
}

这个是被 discussion 里面一个思路激发导致的一个算法, 不过这个算法并不对, input3就过不了;
但是这个算法最后还是错的, input6这个是过不了的, 因为我这里的思路还是加法思路, 加法思路就难免要被 overflow 流整;

不过总体来说, 这个算法还是很多值得学习的地方的:
我们在真正的算法设计的时候, 虽然碰到了这样的 optimization 的问题, 很多时候还是要用 imperitive 的思路来做. 而 imperative 的一个关键就是, 要有一个明确的 instruction 的内容. 什么 loop, loop 里干什么, 什么时候停止, 等等; 当然, 怎样的 instruction 才能获得真正的 optimization, 这个就只能靠自己根据具体的题目去摸索了. 很多时候就算是没有把握, 甚至是没有思路, 也最好还是试一试看看再说;

一个小细节:

            for (int i = 0; i < n && i != maxIndex; i++) nums[i]++;

这个循环跟我上面代码实际写的循环有区别的. 这里i != maxIndex的判断一定要放到 body 里面而不是 header 上面, 因为一碰到这个的话, 如果不满足, loop 就直接停止了. && in header is equivalent to if in body, 这个只限于在 conditional 上面. 在讨论 loop 的时候未必适用;

最后把 sum 的 type 换成了 long, 是可以对付这个 case 了, 不过时间很慢, 如果 submit 的话, 估计是会超时的;

Problem Description

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]
Difficulty:Easy
Category:Algorithms
Acceptance:46.92%
Contributor: amehrotra2610
Companines
Indeed Coursera
Related Topics
math
Similar question
Minimum Moves to Equal Array Elements II