LeetCode 筆記 - 31. Next Permutation

Posted on

題目在此 31. Next Permutation

給定一個整數陣列 nums，請找出其下一個排列方式。排列方式是指將陣列中的數字重新排列成字典序中下一個較大的排列。如果不存在較大的排列，則將陣列重新排列成字典序中最小的排列（即升冪排列）。

例如：

  • nums = [1,2,3]，會回傳 [1,3,2]
  • nums = [3,2,1]，會回傳 [1,2,3]
  • nums = [1,1,5]，會回傳 [1,5,1]

解題思維

這題的目標就是找出下一個排列方式，讓整體比目前的排列方式大一點點。

而要讓數字的變化最小，我們應該優先從尾巴開始找起，因為尾巴的數字變化對整體的影響最小。

所以第一步就是從尾巴開始找，找到第一個下降的數字，這個數字就是我們要變動的數字。因為我們要找到第一個可以變動的數字，這樣才能確保整體的變化最小。
所以我們從尾巴開始找，找到第一個下降的數字，記錄下這個數字的索引為 pivot。

接著第二步就是在 pivot 的右邊數字中，找到第一個比 nums[pivot] 大的數字，這個數字就是我們要交換的數字。但因為我們要讓整體變化最小，所以我們要找到一個只比 nums[pivot] 大的數字，這樣才能確保整體的變化最小。
記錄下這個數字的索引為 min_pivot。

接著第三步就是交換 nums[pivot] 和 nums[min_pivot]。

最後第四步就是將 pivot 右邊的數字反轉，這是因為第一步的搜尋過程中，pivot 右邊的數字一定是遞減的，所以反轉後就是遞增的，這樣就避開了重新排序的時間複雜度。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        # step 1: find the first decrease number from tail
        # step 2: find the first number bigger than the first decrease number from tail
        # step 3: swap the two numbers from step1 and step 2.
        # step 4: reverse the list after the index of the first decrease number

        size = len(nums)

        # 從左邊找到下降的數字

        pivot = size - 2
        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1

        if pivot == -1:
            nums.reverse()
            return

        # 從左邊找到大於 nums[pivot] 的最小數字

        pivot_2 = size - 1
        min_pivot = 0
        min_v = inf
        while pivot < pivot_2:
            if nums[pivot] >= nums[pivot_2]:
                pivot_2 -= 1
                continue

            if nums[pivot_2] < min_v:
                min_v = nums[pivot_2]
                min_pivot = pivot_2

            pivot_2 -= 1

        nums[pivot], nums[min_pivot] = nums[min_pivot], nums[pivot]

        nums[pivot + 1:] = reversed(nums[pivot + 1:])

也許你也會想看看