前往
大廳
主題

LeetCode - 453. Minimum Moves to Equal Array Elements 解題心得

Not In My Back Yard | 2020-10-25 00:00:02 | 巴幣 0 | 人氣 209

題目連結:


題目意譯:
給定一個非空、大小為 n 的整數陣列。找到最少所需的操作數來讓陣列中的元素全部相等。其中,一個「操作」定為將陣列其中的 n - 1 個元素加 1 。



範例測資:
輸入:
[1,2,3]
輸出:
3
解釋:
最少只需三次操作(記住,在此每個操作會使兩個元素增加)
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]


解題思維:
定義 S 為陣列中所有數字的和、 M 為陣列中最小的數字。因為最後所有數字都要相等,因此我們假設最終所有數字皆為 X 。

可以看到每次的操作會使得所有數字的總和加上 n - 1(不論你加在哪些數字上)。我們假設 K 次操作之後可以將所有數字變為 X ,由此可以得到
S + K × (n - 1) = n × X
所以倘若我們知道 X ,便可以從上式推得 K 值。

觀察幾個數列的操作過程(當然是以最少的操作數為前提),可以看出一件事:當前陣列中最小的數字(若有多個最小,則為其中一個)本次操作必定增加。因為如果本次操作不增加該數(也就是增加其他的 n - 1 個數字)的話,則該數與最大的數字的差值會變大,就將不會得到最少的操作數了。

因為最小的數字一直在增加,且增加了 K 次。因此,我們可以得出 X 應為 M + K 。

因此我們可以將 X 套回式子 S + K × (n - 1) = n × X 得到
S + K × (n - 1) = n × (M + K)
移項之後得到
K = S - n × M

因此,所求的最少步數即為 S - n × M。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作