LeetCode 453 Minimum Moves to Equal Array Elements

LeetCode

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment n - 1 elements of the array by 1.

Example 1:

Input: nums = [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]

Example 2:

Input: nums = [1,1,1]
Output: 0

Constraints:

n == nums.length 1 <= nums.length <= 10<sup>5</sup>
-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup> The answer is guaranteed to fit in a 32-bit integer.

题目大意：

求最小移动步数使得数组所有数相等。每次移动是将n-1个元素加1

解题思路：

最小值考虑用DP。但比较难写递归式，以[1, 2, 3]为例，值为3，现在是[1, 2, 3, 6]，由于dp[3]的最终状态为[4, 4, 4], 而最终状态加上新元素为[4, 4, 4, 9], 由6变成9是因为dp[3] = 3，表示移动了3步，新元素6，移动的3步全部参与了，所以变成9
由[4, 4, 4, 9], 4变9，需要5步，所以结果dp[4] = dp[3] + 5 = 8

公式为

dp[i + 1] = dp[i] + (nums[i] + dp[i] - equal_num)  
equal_num = nums[i] + dp[i]

解题步骤：

N/A

注意事项：

1. 数组要排序
2. equal_num初始值为nums[0]

Python代码：

def minMoves(self, nums: List[int]) -> int:
	nums.sort()
	dp, equal_num = 0, nums[0]
	for n in nums:
		dp, equal_num = dp + (n + dp - equal_num), n + dp # 2
	return dp

算法分析：

时间复杂度为O(n)，空间复杂度O(1)