【Leetcode】python – [31] Next Permutation 個人解法筆記

➣ Reading Time: 8 minutes

題目出處

31. Next Permutation

難度

medium

個人範例程式碼

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return nums

        last = len(nums)-1
        while(last > 0):
            if nums[last-1] < nums[last]: # ...last-2, last-1, last # 34 -> 43  
                self.change_inplace(nums, last-1) 
                return 
            last -= 1

        else: # all descend
            # nums.reverse() 
            self.inplace_reverse(nums, 0, len(nums)-1)
            return 

    def change_inplace(self, nums, idx):
        change_idx = self.find_next_same_or_bigger(nums, idx)
        nums[change_idx], nums[idx] = nums[idx], nums[change_idx] # inplace
        self.inplace_reverse(nums, idx+1, len(nums)-1) # inplace reverse after idx, nums[:idx]
        return 

    def find_next_same_or_bigger(self, nums, idx):
        last = len(nums)-1
        target = nums[idx]
        while nums[last] <= target:
            last -= 1
        else:
            return last

    def inplace_reverse(self, nums, start, end):
        while(start < end):
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
            print(nums)
        return 

算法說明

排列問題的進階版,求「下一個排列」,
直接的做法可以簡單歸納為,

  1. 從結尾處開始找「第一個」往下的地方
  2. 如果找到了,交換「往下的那個」與「之前往上的過程中 <= 此數的數字 (注意等於)」,交換後把整個數列顛倒
  3. 如果找不到,下一個數字就是全部順序直接顛倒 (也就是第一個數字)

圖片說明

我們找第一個往下的地方,上面我們有標示箭頭,
將「在下的位置」與「之前上升時,>= 下降數的第一個數字」交換

注意這邊可以多留意 [1,1,5] -> [1.5.1] 這個 case,可以解釋為何要處理 「>=」

交換後,我們會發現之前的上升順序還是會保持上升,我們直接顛倒方向,使後綴的部分呈現下降順序。

以文字說明 – 1 (邊看圖想會比較懂在做什麼):

  1. 1243 我們抓到下降的 4->2,
  2. 2 與第一個 3 (>=2)交換,此時為 1342,
  3. 把交換處之後的倒序,變成 1324,就是下一個數字

以文字說明 – 2 (邊看圖想會比較懂在做什麼):

  1. 1342 我們抓到下降的 4->3,
  2. 3 與第一個 4 (>= 3)交換,此時為 1432,
  3. 把交換處之後的倒序,變成 1423,就是下一個數字

最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解

  • 這邊也可以參考 leetcode 上很讚的圖片說明版:

Easy python solution based on lexicographical permutation algorithm

input handling

如果沒有 nums,回傳 nums

Boundary conditions

做完上述的交換後,return 結果

Reference

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 728

★留個言吧!內容有誤或想要補充也歡迎與我討論!