题意:一次操作,n元数组中任意n-1个数+1。求取最小操作次数使得数组所有元素相等。
分析:
1.正面思考,每次将数组中除最大值以外的所有值+1,直到所有元素都相等。
2.反面思考,每次将数组中的最大值-1,直到所有元素相等(最少操作次数=数组和-n*数组最小值)
n元数组,其中n-1元+1,因为只要求元素相等,可以不考虑值,可以整体再-1,两次操作后也就是一元-1。
反面思考数学证明:
假设所有元素都相等时数字为k, 如果最小数字经过x次移动能够等于k, 则此时所有元素也能等于k, 此时移动次数为k-min(nums).
则有方程: 数组元素总和增加量 = 终止时数组元素总和 - 开始时数组元素总和
即方程: (k-min(nums)) * (n-1) = k * n - sum(nums)
求解后: k = sum(nums) - min(nums) * (n-1)
则可以得到最小移动次数 k-min(nums)
1 class Solution { 2 public int minMoves(int[] nums) { 3 if(nums==null) return 0; 4 int min=Integer.MAX_VALUE,sum=0; 5 for(int num:nums){ 6 sum+=num; 7 if(min>num) min=num; 8 } 9 return sum-nums.length*min; 10 } 11 }