LC31-下一个排列（数组游戏）

题目

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

虽然是全排列扩展题，但是个人认为和全排列没有什么关系。
图来自于LeetCode题解。

1df4ae7eb275ba4ab944521f99c84d782d17df804d5c15e249881bafcf106173-file_1555696082944.gif

主要是思路。

1、先找出最大的索引 k 满足 nums[k] < nums[k+1]，如果不存在，就翻转整个数组；
2、再找出另一个最大索引 l 满足 nums[l] > nums[k]；
3、交换 nums[l] 和 nums[k]；
4、最后翻转 nums[k+1:]。

作者：powcai
链接：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
     //用库应该容易实现
        if(nums.size()>1){
            int i=nums.size()-1;
            int j=nums.size()-2;
            
            while(nums[i]<=nums[j]&&j>=1){
                i--;
                j--;
            }
            if(nums[i]>nums[j]){
                int index=i;
                while(index<nums.size()&&nums[index]>nums[j]){
                    index++;
                }
                
                 swap(nums[index-1],nums[j]);
                 sort(nums.begin()+j+1,nums.end());
                 return;
            }
                
        }
            
        
        
        sort(nums.begin(),nums.end());
         
    }
};