🔗 🟡 31. Next Permutation

題意

整數陣列的一個 排列 是其成員按順序排列的一種方式。

  • 例如，對於 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，找出 nums 的下一個排列。

替換必須在 原地(in-place) 進行，並且只能使用 常數級額外的記憶體。

思路：兩遍遍歷

為了方便說明，首先忽略不存在下一個更大的排列的情況，即總是存在下一個更大的排列。

由於要找到在所有比當前排列大的排列中，字典序最小的排列，我們應盡可能少修改 nums 前方的元素。換句話說，如果我們可以透過交換最後的 kk 個元素，得到更大的排列，那麼在 kk 最小的情況，我們可以得到恰好緊跟在 nums 之後的排列。

如此便可以確定核心思路，從 k=2k=2 開始，依次檢查是否能改變最後 kk 個元素得到更大的排列。

  • 不難發現若無法交換，則最後 kk 個元素一定是由大到小非遞增的，因此當 可以交換時必定滿足 nums[i]<nums[i+1]≥nums[i+2]≥...≥nums[n−1]nums[i] < nums[i+1] \geq nums[i+2] \geq ... \geq nums[n-1] 的形式。
  • 將指標 ii 由後往前遍歷，找到第一個滿足 nums[i]<nums[i+1]nums[i] < nums[i+1] 的位置，即為可以交換的位置。

為得到在大於當前排列中最小的排列，應交換後續元素中比 nums[i]nums[i] 大的元素中最小的那個，並且讓後續元素由小到大非遞減排序。

  • 但這裡 不需要真的排序 ，可以利用上述性質，將 nums[i]nums[i] 與後續元素中比 nums[i]nums[i] 大的元素中最小的那個交換後，此時必定滿足 nums[j]<nums[i+1]≥...≥nums[i]≥...≥nums[n−1]nums[j] < nums[i+1] \geq ... \geq nums[i] \geq ... \geq nums[n-1]，即已經按照由大到小非遞增排序，故只要翻轉 nums[i+1:]nums[i+1:] 即可

如果 i<0i < 0，則表示 nums 已經是最大排列，無法透過交換得到更大的排列。根據題意，其下個排列為最小排列，故翻轉 numsnums 即可，由於此時 i=−1i=-1，等同於翻轉 nums[i+1:]nums[i+1:]

複雜度分析

  • 時間複雜度：O(n)O(n)，其中 nn 是 nums 的長度。
  • 空間複雜度：O(1)O(1)，僅使用常數級額外空間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # 由後往前找到第一個滿足 nums[i] < nums[i+1] 的位置
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        # 此時 nums[i] < nums[i+1] >= nums[i+2] >= ... >= nums[n-1]
        # 如果 i < 0，則 nums 已經是最大排列，根據題意，其下個排列為最小排列，故翻轉 nums 即可
        if i >= 0:
            # 由後往前找到第一個大於 nums[i] 的元素 nums[j]，交換兩者
            # 此時 nums[j] < nums[i+1] >= ... >= nums[i] >= ... >= nums[n-1]
            # 翻轉 nums[i+1:] 即為答案
            j = n - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # 兩種情況的翻轉可以寫在一起
        nums[i+1:] = nums[i+1:][::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
      int j = n - 1;
      while (j >= 0 && nums[j] <= nums[i]) j--;
      swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
  }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

1other, solo, no humans, Sylveon, Sylveon (Pokémon), Pokémon, blue eyes, full body, outdoors, sky, day, o, blue sky, grass, grassland, looking up,

A serene hand-drawn scene featuring Sylveon, a Pokémon with flowing ribbons, standing in a vibrant green meadow under a clear blue sky. Its eyes are blue, and its ears are a vibrant shade of pink, while its tail is a lighter shade of gray. The ribbons are gently swaying in the wind, and the art style is soft and painterly, emphasizing tranquility and freedom. Detailed grass in the foreground contrasts with the bright, open sky.

前幾天在群組回答了同樣的問題，既然都回答了，就順便寫成文章吧。

但我不知道具體是哪間學校哪年的考試，如果有人知道，歡迎留言告知。