31. Next Permutation

難度: Medium

類型: Array, Two Pointers

CPP程式下載: 31.cpp

前情題要:

下一個排序的數列。排列必須就地(in-place)完成, 並且使用常數的額外記憶體。

排列的順序一開始是從小到大, 直到最後是從大到小, 在輪迴成從小到大。

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.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

思考方式:

1. 想出排序的邏輯很重要。懂, 但是沒辦法用數學方式表達, 就很難寫出好方法。

2. 規則是如果排序是從大到小, 那就是最後一個組合, 就要改成從小到大。

3. 從最後一個數往前看(數列倒過來看), 如果是從小到大, 那就找不到更大的組合。

4. 如果找到一個數, 比後面那個數小, 那從這個數字開始往後是可以組成更大的組合。

5. 接著就是要找出最接近但是更大的組合。 那就從最後面的數字開始往前找(這裡如果用1/2位置比較, 能夠更快, 但這不是這題的重點, 這邊我偷懶了), 直到找到比這個數字大的數字, 然後兩個互相交換位置。

6. 把右邊剩下的數字從小到大(從左到右)排列。

7. 因為右邊剩下的數字是從大到小, 要改成從小到大, 就最左跟最右兩兩互換, 直到中間。

8. 如果整個數列找完, 發現是從大到小排列, 那就改成從大到小排列, 就是答案。

複雜度思考:

Time Complexity: Worst case: O( N+N/2 )

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 15.72 MB, Beats: 32.29%

Accepted

266 / 266 testcases passed

tendchen

submitted at Nov 10, 2025 22:39

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

15.72MB

Beats32.29%

Analyze Complexity

Code

C++

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int iSize = nums.size();
        int i,j;
        int itemp;
        //cout << "iSize=" << iSize << "\n";
        for (i=iSize-1;i>0;i--)
        {
            //cout << "i=" << i << "\n";
            if (nums[i-1]>=nums[i])
            {
                //cout << "continue!" << "\n";
                continue;
            }
            else
            {
                //cout << "else!" << "\n";
                //cout << "i=" << i << "\n";
                for (j=iSize-1;j>=i;j--)
                {

                    if (nums[j]>nums[i-1])
                    {
                        //cout << "i=" << i << ", j=" << j << "\n";
                        itemp=nums[i-1];
                        nums[i-1]=nums[j];
                        nums[j]=itemp;
                        j=1;
                        for (;i<iSize;i++)
                        {
                            if (i<(iSize-j))
                            {
                                itemp=nums[i];
                                nums[i]=nums[iSize-j];
                                nums[iSize-j]=itemp;
                            }
                            else
                            {
                                return;
                            }
                            j++;
                        }
                    }
                }
            }
        }
        j=1;
        for (;i<iSize;i++)
        {
            if (i<(iSize-j))
            {
                itemp=nums[i];
                nums[i]=nums[iSize-j];
                nums[iSize-j]=itemp;
            }
            else
            {
                return;
            }
            j++;
        }
    }
};