LeetCode 筆記 - 462. Minimum Moves to Equal Array Elements II

題目在此 462. Minimum Moves to Equal Array Elements II

給定一個數列,每一步可以選定一格加 1 或減 1
請給出讓每個數字都相等的最小步驟

解題思維

如果沒寫過前一題可以先看一下
453. Minimum Moves to Equal Array Elements

剛看到這題的直覺是把所有數字都帶到平均值
但這個策略其實會增加移動成本

在這裡我們先有一個概念

現在有兩個數字 ab 還有一個相遇點 meet point 寫為 m
只要 mab 之間,那麼移動成本就會固定為 abs(a - b)
也就是說如果 mab 之外的範圍,都會增加移動成本

好,具備這個概念之後,我們來看一個數列的情況

一個數列勢必存在 max valuemin value
而移動至 max valuemin value 之間的任一點,成本都是相同的

好,我們再近一步

將剛剛的 max valuemin value 拿掉
就會出現新的 max value 2min value 2
而移動至 max value 2min value 2 之間的任一點,成本都是相同的

有感覺到了嗎?這問題的核心是在找到不會讓移動成本增加的點
而我們持續移除 max valuemin value 的最終結果

就是 Median

所以找到中位數,然後計算移動成本就完成了 🥹

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def minMoves2(self, nums):

if (size := len(nums)) == 1:
return 0

nums.sort()
median = size // 2

result = 0
for i in range(size):
result += abs(nums[i] - nums[median])

return result

相關文章