主題

LeetCode - 31. Next Permutation 解題心得

Not In My Back Yard | 2021-07-04 00:00:04 | 巴幣 0 | 人氣 92

題目連結:


題目意譯:
實作「下一個排列」,其將數字重新排列成下一個較大字典序的數字排列。

如果不可能有這樣子的排列,則它應重新排列為最低可能的字典序順序(即以升序排列)

交換過程中必須原地(In-Place)完成並使用常數數量級的額外記憶體。

限制:
1 ≦ nums.length ≦ 100
0 ≦ nums[i] ≦ 100



範例測資:
範例 1:
輸入: nums = [1,2,3]
輸出: [1,3,2]

範例 2:
輸入: nums = [3,2,1]
輸出: [1,2,3]

範例 3:
輸入: nums = [1,1,5]
輸出: [1,5,1]

範例 4:
輸入: nums = [1]
輸出: [1]


解題思維:
首先,我們先討論什麼樣的情況沒有「下一個」排列。可以看到
3 2 1
5 1 1
9 8 7 6
都沒有下一個排列。而
3 1 2
1 1 5
7 9 8 6
有著下一個排列。

因此給定的數列為非嚴格遞減時,代表著該數列沒有下一個排列。

而我們可以從「7 9 8 6」的結尾「9 8 6」看到:這個子數列本身沒有著下一個排列,但是整個數列卻有著下一個排列,因此這代表著我們要從新的「開頭」重新排列。

也就是說我們需要將開頭的「7」替換成下一個較大的數字,而在本例中其值為「8」,因為「8」是「9 8 6」中大於「7」並其值最接近「7」的數字。

所以我們數字「7」和「8」交換得到「8 9 7 6」。那剩下的數字怎麼辦呢?因為它應該要是「8」開頭的第一個排列,所以我們需要將「8」右邊的數字由小排到大,得「8 6 7 9」。而這即是「7 9 8 6」 的下一個排列。



因此,我們可以對於給定的 nums 陣列利用以上策略去找到下一個排列:
一開始我們從 nums 從尾掃到頭。如果一路都是非嚴格遞增(因為正著看是非嚴格遞減,反過來就會變成非嚴格遞增)的話,則代表 nums 沒有下一個排列,此時我們需要將 nums 由小排到大(根據題目所求)。

如果有不是非嚴格遞增的狀況發生,意即我們找到了一個索引值 i 滿足:nums[i] < nums[i + 1]。則我們就從索引值 i 開始往尾端跑去找到大於 nums[i] 但是要盡可能接近 nums[i] 之值的數字。然後我們將該數字與 nums[i] 交換。交換後把 nums[i] 右側的數字全數由小排到大,即可得到下一個排列。




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

創作回應

更多創作