Leetcode 453 Minimum Moves to Equal Array Elements

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)

Screen Shot 2018-01-19 at 6.07.55 PM

解法二:

针对解法一,我们可以进行一个优化。 其实也可以这么算,省去排序的时间,维护一个min的变量,最后用整个数组的和减掉min*数组的长度。

时间复杂度 n

空间复杂度 O(1)

 

Screen Shot 2018-01-19 at 6.08.18 PM

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s