31. Next Permutation

发表于 | 分类于

每日一题 2019 - 03 - 14

题目:

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 and use only constant 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,2,3` → `1,3,2`
`3,2,1` → `1,2,3`
`1,1,5` → `1,5,1

解法：

这个题让我们找出当前序列中的下一个全排列序列，如果当前全排列序列为最大的顺序，则将其转换为初始序列。

思路大概如下，设给定数字串为A[N]，令 i = n - 1

  • 从数字串后面往前走，找到 A[i] > A[i-1] 的位置 i，那么证明从n-1到i为递减的序列
  • 从 i 到 N - 1 中找出一个比A[i-1]大的数字A[temp]，然后交换A[i-1]与A[temp]
  • 由于此时后N-i+1位已经进入了下一个全排列的状态，将后N-i+1位翻转，即得到下一个全排列序列
  • 如果给定序列本身就是降序，那么直接翻转

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int n = num.size();
        if(n == 1) return;
        
        for(int i = n-2, ii = n-1; i >= 0; i--, ii--)
        {
            //找到第一组相邻的降序组合
            if(num[i] < num[ii])
            {
                //找到i-1之后第一个大于num[i-1]的数字，并交换
                int j = n - 1;
                while(num[i] >= num[j]) j--;
                swap(num[i], num[j]);
                //交换后，仍然是降序排列。
                reverse(num.begin() + ii, num.end());
                return;
            }
        }
        //如果排列是递减有序的，翻转整个数组
        reverse(num.begin(), num.end());
        return;
    }
};
0%
undefined