Next Permutation

左手的ㄟ右手 2022-06-06 04:42 160阅读 0赞

# 题目 #

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.  
`1,2,3` → `1,3,2`  
`3,2,1` → `1,2,3`  
`1,1,5` → `1,5,1`

# ``分析 #

## 1. 题目要求 ##

给出某个全排列中的一个排列，求出该排列的下一个排列。例如，对于排列\[1, 3, 2\]，其下一个排列为\[2, 1, 3\]。当该排列为最后一个排列时，其下一个排列为该全排列的第一个排列。

对于1， 2， 3，其全排列的顺序如下：

\[1, 2, 3\]->\[1, 3, 2\]->\[2, 1, 3\]->\[2, 3, 1\]->\[3, 1, 2\]->\[3, 2, 1\]

## 2. 求解方法 ##

对于一个全排列中的某一个排列P = p(1)p(2)p(3)...p(n)

（1）找到：j=max\{i|p(i) < p(i \+ 1)\} ，k=max\{i|p(i) > p(j)\}，即后向前找到第一个p(i) < p(i + 1)的位置 j = i，再从最后面开始往前找，找到第一个p(k) > p(j)的位置。

（2）交换p(j)和p(k)的值。

（3）翻转 j（不包括 j） 之后的所有值。

最终得到：P' = p(1)p(2)...p(j - 1)p(k)p(n)p(n - 1)...p(k+1)

例如：对于排列：3,4,6,9,8,7,5,2,1

由步骤（1）找到 j = 3, 使得p(3) = 6 < 9 = p(4), k = 6，使得p(6) = 7 > 6

由步骤2得到p(3) = 7, p(6) = 7.此时排列为：3, 4, 7, 9, 8, 6, 5, 2, 1

由步骤3可得到最终的结果：3, 4, 7, 1, 2, 5, 6, 8, 9

注：如果P为排列的最后一个排列，即对于所有的i < n, 有p(i) >= p (i + 1)。此时直接翻转整个排列，得到P' = p(n)p(n - 1)...p(1)

## 3. 代码如下 ##

class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int i, j, k;
            int temp;
            int n = nums.size();
            for (i = n - 1; i > 0; i--) {
                if (nums[i-1] < nums[i]) {
                    for (j = n - 1; j > i - 1; j--) {
                        if (nums[j] > nums[i - 1]) {
                            temp = nums[i - 1];
                            nums[i - 1] = nums[j];
                            nums[j] = temp;
                            break;
                        }
                    }
                    for (j = 1, k = i; j <= (n - i)/2; j++, k++) {
                        temp = nums[k];
                        nums[k] = nums[n - j];
                        nums[n - j] = temp;
                    }
                    break;
                }
            }
            if (i == 0) {
                for (j = 0; j <= (n - 1) / 2; j++) {
                    temp = nums[j];
                    nums[j] = nums[n - j - 1];
                    nums[n - j - 1] = temp;
                }
            }
        }
    };