今天是紀錄LeetCode解題的第三十一天

第三十一題題目：A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.

給定一個由整數組成的陣列nums，代表一個排列，將這個排列重新排列成字典序中「下一個」更大的排列，如果已經是字典序中最大的排列，那麼就將它重新排列為最小的排列（即升序排列）。
必須就地（in-place）修改，只能使用常數額外空間

例如，對於arr = [1,2,3]的所有排列arr：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

• arr = [1,2,3]的下一個排列是[1,3,2]
• 類似的arr = [2,3,1]的下一個排列是[3,1,2]
• 而arr = [3,2,1]的下一個排列是[1,2,3]，因為[3,2,1]沒有字典順序更大的排列

解題思路

• 從右往左找「第一個下降點」
  這個位置之後是「遞減序列」，已經是當前排列的尾巴（最大排列的尾巴）
  例如nums = [1,4,3,2]，1 < 4 → 找到「第一個下降點」在 index = 0
• 從右往左找比nums[i]大的最小數
  nums[i] = nums[0] = 1 → 找到2 > 1， index = 3，然後交換nums = [2,4,3,1]
• 把 i 之後的部分反轉
  i之後的部分是[4,3,1]反轉後[1,3,4]
  所以最後答案[1,4,3,2]的下一個排列是[2,1,3,4]

程式碼

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2 #從倒數第二個開始
        while i >= 0 and nums[i] >= nums[i + 1]: #找到第一個「升序違反」的位置
            i -= 1
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]: #從右找比nums[i]大的數
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # 翻轉i之後的所有數
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

執行過程

初始狀態

• nums = [1,4,3,2]
• n = len(nums) = 4
• i = n - 2 = 2

找第一個下降點

• while i >= 0 and nums[i] >= nums[i + 1] → nums[2] >= nums[3] → 3 > 2 → True
• i -= 1 → i = 1

• while i >= 0 and nums[i] >= nums[i + 1] → nums[1] >= nums[2] → 4 > 3 → True
• i -= 1 → i = 0

• while i >= 0 and nums[i] >= nums[i + 1] → nums[0] >= nums[1] → 1 > 4 → False

從右往左找比nums[i]大的最小數

• j = n - 1 = 4 - 1 = 3
• while nums[j] <= nums[i] → 2 <= 1 → False

交換

• nums[i], nums[j] = nums[j], nums[i] → nums[0] = 2 、 nums[3] = 1
  nums = [2,4,3,1]

翻轉i之後的所有數

• left = i + 1 = 1
• right = n - 1 = 3
• while left < right → 1 < 3 → True
• nums[left], nums[right] = nums[right], nums[left] → nums[1] = 1 、 nums[3] = 4
  nums = [2,1,3,4]
• left += 1 = 2
• right -= 1 = 2
• while left < right → 2 < 2 → False → 結束迴圈

最後的答案就是[2,1,3,4]，這題不須回傳，會自動檢查nums