题目描述
给定一个长度为 n
的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1
个元素增加 1
。
样例
输入:
[1,2,3]
输出:
3
解释:
只需要3次移动(注意每次移动会增加两个元素的值):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
算法分析
最小移动次数使数组元素相等,只关心让元素是一致即可
从相对方向来看:将除了一个元素之外的全部元素+1
,等价于将该元素-1
,找到最小值minv
,枚举整个数组,累计nums[i] - minv
差值的总和
时间复杂度 $O(n)$
Java 代码
class Solution {
public int minMoves(int[] nums) {
int n = nums.length;
if(n == 1) return 0;
int minv = 0x3f3f3f3f;
for(int i = 0;i < n;i ++)
{
minv = Math.min(minv, nums[i]);
}
int res = 0;
for(int i = 0;i < n;i ++)
res += nums[i] - minv;
return res;
}
}