LeetCode Next Permutation 题解

发表于 | 分类于 | 阅读次数:
字数统计: 565 字

LeetCode Next Permutation 题解

题意

题目的意思就是求给定序列的下一个字典序

题解

首先我们要了解什么是字典序，这里参考wiki的解释：

设想一本英语字典里的单词，何者在前何者在后？

显然的做法是先按照第一个字母、以 a、b、c……z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，sigh 和 sight），那么把短者排在前。

通过这种方法，我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串，而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序

我的理解是：把一组数的所有排列情况按照字母顺序进行一次排序得到的就是一个字典序

在这道题中要求给定排列的下一个字典序，可以知道把一个大一点的数往前移动这个序列的字典序一定会变大，那么就要从后往前找到第一个能变大的数（变大指和它后面的某个数互换以后），找到这个数以后把他和比他大的“第一个”数互换获得最小的增量，然后把这个数后面的数字按照从小到大的顺序重新排列。

举个例子：

enter description here

代码(C++)

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
26
27
28
29
30
31
32
33
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int first = nums.size(), len = nums.size();
        // 倒序查找第一个升序数
        for(int i=len-1; i>0;--i)
        {
            if(nums[i] > nums[i-1])
            {
                first = i-1;
                break;
            }
        }
        if(first == len)
            reverse(nums.begin(), nums.end());
        else
        {
            int second = len-1;
            // 在后面找一个刚好比这个数大一点的数和其互换
            for(int i=first + 1;i<len;++i)
            {
                if(nums[i]<=nums[first])
                {
                    second = i-1;
                    break;
                }
            }
            swap(nums[first], nums[second]);
            // 反转后面的部分
            reverse(nums.begin()+first+1, nums.end());
        }
    }
};

更多LeetCode题解，欢迎查看我的GitHub项目