453. 最小移动次数使数组元素相等(数学)

453. 最小移动次数使数组元素相等(数学)

题意:一次操作,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 }

453. 最小移动次数使数组元素相等(数学)

上一篇:MyBatis的ResultMapping和ResultMap


下一篇:下拉框移动 jquery