
问题
给定一个长度为 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 的时间复杂度基于部分函数库的实现,它们的时间复杂度应当均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3877。