本文共 1386 字，大约阅读时间需要 4 分钟。

题目

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.

AC代码

思路很简答，就是利用下一个全排列性质，具体见上一博客。

class Solution {public:    void nextPermutation(vector
   
    & nums) {        //先检查nums中是不是递减的        bool decending=true;//假设递减        for(int i=0;i
    
     =1;i--)            {                if(nums[i]<=nums[i-1]) continue;//有等号是为了考虑重复元素                else                 {                    pivot=nums[i-1];                    p_index=i-1;//记录pivot的下标                    break;                }            }            //然后寻找右边最大递减子序列所有比pivot大的元素中最小的那个，和pivot交换            for(int i=nums.size()-1;i>=0;i--)            {                if(nums[i]>pivot)//一定要找到严格大于pivot的，不能带等号，肯定会有的                {                    swap(nums[i],nums[p_index]);                    break;                }            }            //然后调换右边最大递减子序列的顺序            for(int i=p_index+1;i<=(p_index+nums.size())/2;i++)                swap(nums[i],nums[nums.size()+p_index-i]);        }    }};
    
   

转载地址：http://pexvi.baihongyu.com/