453. 最小操作次数使数组元素相等
source link: https://sexywp.com/453-min-moves.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
453. 最小操作次数使数组元素相等
这道题虽然是简单，但是一看这复杂的操作，我就彻底懵逼了。每次将 n-1 个数字加一，最后要所有的数字相等。
这是太抽象的一个过程，脑海里自然联想到了滑块拼图之类的东西，或者覆盖问题，想得极其复杂，所以马上就不知道怎么做了。然后还草稿上画了很多，找这个问题的规律。找了半天也没找到。
暴力解，就是照着题目意思去做，我们想到的就是贪心法，每次挑出最大的一个，其他都加一，然后重复这个过程，直到所有的都相等为止。我想到了这个算法，但是一时半会儿也不能证明这个就是正确的操作法，因题目要求最小的次数。谁知道贪心法的次数是不是最小呢？
所以我就看答案了，果然这个就是最小，有时候做算法题看来也只能靠大胆了。这种根本不用证明的。。。猜一个就是了。猜错就跪了呗。
然后我看到官方题解竟然想出了四种解题方法，第一种就是我说的暴力法，照字面意思硬做。果然，超时，因为是 O(n^2) 的解法啊，肯定过不了。然后第二种是，每次不是加一了，而是直接加 最大值与最小值的 diff，这样可以少加几次。你这么说我当然明白，但是怎么证明这个加法和原来那个加法是等价的呢？也是靠猜就行了？这并不显然啊！！
第三种解法是什么动态规划，我就更懵逼了，根本不是人话好不好，我至今也没看懂。直到最后一个解法出现，我才明白过来。不过官方题解仍然不是用人话写的，我看了一个网友用人话写了，才终于恍然大悟，原来这么简单。
把 n-1 个数字都加一，其实相当于把最大值减 1，这样每次操作 n – 1 个数的抽象复杂情况，变成了一个极其简单的情况，每次挑最大值减 1，这就太简单了。最少肯定是所有值都减到最小值就可以了。太牛了，于是，就是很容易写出一个 O(n) 算法了。在一次遍历中，找到最小值，顺便找出所有数字的和，然后做个减法就完事了。
class Solution:
def minMoves(self, nums: List[int]) -> int:
nums.sort()
res = 0
for i in reversed(range(1, len(nums))):
res += nums[i] - nums[0]
return res
最牛逼的 O(n) 算法我就不写了，大家自己写吧，上面这个是我写的 O(nlogn) 的算法，排序后，把所有数字和最小值的差求个和。
给我的启发：
- 试试逆向思维，不要忘记这一点；
- 虽然想明白后一点不难写，但是很多时候，题目难都在模型的转换上面，你看到的是假象。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK