<div>
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:
<pre>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] </pre>
Example 2:
<pre>Input: nums = [1,1,1] Output: 0 </pre>
Constraints:
n == nums.length1 <= 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.
</div>
题目大意：
求最小移动步数使得数组所有数相等。每次移动是将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
公式为
1
2dp[i + 1] = dp[i] + (nums[i] + dp[i] - equal_num)
equal_num = nums[i] + dp[i]
解题步骤：
N/A
注意事项：
- 数组要排序
- equal_num初始值为nums[0]
Python代码：
1
2
3
4
5
6def 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)
