数据结构学习 leetcode31 下一个排列

关键词：下一个排列 字典序 排列

这是我在做jz38字符串的排序的时候，一种解题方法是字典序，用到的就是这种方法。这种方法支持不重复地输出全排列。

题目：下一个排列

思路：

我看了官方题解和这位大哥的题解，建议直接看他们吧！

这个题需要记一记。两次扫描，找较小值和较大值。

复杂度计算：

时间复杂度O(n) 两次扫描

空间复杂度O(1)

代码：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i=nums.size()-2;
        while(i>=0&&nums[i]>=nums[i+1])//找小数，从右到左第一个非降序排列的数
        {
            i--;
        }//此时可以知道，[i+1,end)的数都是降序排列的
        if(i>=0)//找到nums[i]<nums[i+1]
        {
            int j=nums.size()-1;
            while(j>=0&&nums[i]>=nums[j])//找大数，从右到左第一个大于小数的数
            {
                j--;
            }
            swap(nums[i],nums[j]);//交换
        }
        reverse(nums.begin()+i+1,nums.end());//区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
    }
};