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]
这道题的意思就是说给你一个数组有i个元素, 每次可以让i – 1个元素的值加1, 求解至少加多少次,整个数组的值全部相等。
解法一:
我们可以这么想,如果让我们选择让那些元素的值加一,我们肯定每次让除了最大的那个元素,其他的元素加一。 那么我们反过来想,其实这就相当于让最大的一个元素减1. 那么一次操作是最大的元素减一, 到最后每个元素都减小到最小那个元素值,这个问题就解决了。比如举个例子:
[1,2,3] -> [1,2,2]-> [1,2,1] -> [1, 1, 1] 所以最后结果是三次,就等价于队列所有元素与最小值的差值。解法一可以先排序,然后算出所有的值与最小值的差值。
时间复杂度 nlog(n)
空间复杂度 O(1)
解法二:
针对解法一,我们可以进行一个优化。 其实也可以这么算,省去排序的时间,维护一个min的变量,最后用整个数组的和减掉min*数组的长度。
时间复杂度 n
空间复杂度 O(1)