C#LeetCode刷题之#453-最小移动次数使数组元素相等（Minimum Moves to Equal Array Elements）

问题

给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n – 1 个元素增加 1。

输入:[1,2,3]

输出:3

解释:只需要3次移动（注意每次移动会增加两个元素的值）：

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

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.

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]

示例

public class Program {

    public static void Main(string[] args) {
        var x = new int[] { 1, 2, 3 };

        var res = MinMoves(x);
        Console.WriteLine(res);

        x = new int[] { 1, 2147483647 };
        res = MinMoves2(x);
        Console.WriteLine(res);

        x = new int[] { 1, 5, 7, 2, 3 };
        res = MinMoves3(x);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int MinMoves(int[] nums) {
        //这个解法未AC，因为nums.Sum()的值有可能会超出整型范围
        return nums.Sum() - nums.Length * nums.Min();
    }

    private static int MinMoves2(int[] nums) {
        var min = nums.Min();
        var sum = 0L;
        foreach (var num in nums) {
            sum += num;
        }
        return (int)(sum - min * nums.Length);
    }

    private static int MinMoves3(int[] nums) {
        var min = nums.Min();
        return nums.Sum(n => n - min);
    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

3
2147483646
13

分析：

该题的解法思路为每次减1个数，使整个数组相等。

显而易见，MinMoves 、MinMoves2 和 MinMoves3 的时间复杂度基于部分函数库的实现，它们的时间复杂度应当均为：  。