[LeetCode解題攻略] 31. Next Permutation

題目描述

實現一個函數來重新排列數字序列，使其成為下一個更大的排列。如果不存在更大的排列，則將其排列為最小的順序（即升序）。

這個排列必須是 "原地" 完成，也就是說，只能使用常數級額外空間。

範例 1:

Input: nums = [1,2,3]
Output: [1,3,2]

範例 2:

Input: nums = [3,2,1]
Output: [1,2,3]

範例 3:

Input: nums = [1,1,5]
Output: [1,5,1]

解法一：雙指針法

思路

1. 從右到左找到第一個數字 nums[i]，使得 nums[i] < nums[i + 1]。
2. 再次從右到左找到第一個數字 nums[j]，使得 nums[j] > nums[i]。
3. 交換 nums[i] 和 nums[j]。
4. 反轉 nums[i+1:]。

此算法的核心是找到一個較小數字的 "替代點"，並通過反轉來確保後續部分是最小的排列。

程式碼實現

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

        # Step 1: 找到第一個 nums[i] < nums[i + 1]
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            # Step 2: 找到第一個 nums[j] > nums[i]
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            # Step 3: 交換 nums[i] 和 nums[j]
            nums[i], nums[j] = nums[j], nums[i]

        # Step 4: 反轉 nums[i + 1:]
        nums[i + 1:] = reversed(nums[i + 1:])

時間與空間複雜度

• 時間複雜度: O(n)，最多遍歷兩次數組。
• 空間複雜度: O(1)，為原地操作。

解法二：暴力法

思路

1. 將當前排列的所有排列生成出來。
2. 找到當前排列後的下一個排列。

該解法的時間複雜度極高，適合用於理解問題，但不適合實際應用。

程式碼實現

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 生成輸入列表的所有排列
        all_perms = sorted(set(permutations(nums)))        
        # 找到當前排列的索引
        current_index = all_perms.index(tuple(nums))        
        # 如果存在下一個排列，則更新 nums
        if current_index + 1 < len(all_perms):
            nums[:] = list(all_perms[current_index + 1])
        else:
            # 如果是最後一個排列，則返回第一個排列（排序後的順序）
            nums[:] = list(all_perms[0])

時間與空間複雜度

• 時間複雜度: O(n!)，生成所有排列的時間成本。
• 空間複雜度: O(n!)，存儲所有排列的空間成本。

總結

1. 雙指針法 是解決此問題的最佳方法，其時間效率高，且使用常數額外空間。
2. 暴力法 雖然直觀，但無法滿足大數據規模下的性能要求。

在實際應用中，應優先使用雙指針法，確保代碼簡潔且性能優越。