453. Minimum Moves to Equal Array Elements
description:
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.
example:
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]
solution
what?
单次移动定义为让数组中的n-1
个元素自增1
,请问最少多少次移动能让数组所有元素相等。
how?
我们并不需要求解最后这个让数组相等的每个元素确切的值,而只要达到数组相等的目的即可。
逆向思维:n-1个数自加 => 1个数自减
这样我们每次move
就只需要考虑一个元素,让所有元素都等于数组中最小的那个元素即可,移动次数为每个元素距离最小值的差值之和。
//3ms
class Solution {
public int minMoves(int[] nums) {
int ans=0;
if(nums.length==1) return ans;
int min=Integer.MAX_VALUE;
//找到最小值
for(int i: nums) {
min=Math.min(i, min);
}
//累加每个数需要移动的次数
for(int i: nums) {
ans += i-min;
}
return ans;
}
}
开始我是这样做的:
按照题意,先排序数组,每次移动让最小的n-1
个元素自增,检查数组所有元素是否相同,然后重新排序,重复上述过程,知道数组中所有元素相等。
这种做法时间复杂度为O(n^2)O(n2),遇到测试用例[0, 2147483647]
时果然超时了。
Complexity
tags
summary
逆向思维解决数学问题
TYH'S BLOGtangyiheng.top