leetcode-31

leetcode 31

// 从右向左找第一个顺序对，在找到的地方向后是按顺序递减的，在从右向左找第一个大于顺序对第一个数的索引，然后交换，
// 将顺序对之后的元素逆转，就是下一个排列
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //next_permutation(nums.begin(), nums.end());
        vector<int>::iterator i, i1, i2;
        // 没有数字 或者 只有一个数字
        if(nums.begin() == nums.end()) return ;
        i = nums.end();
        if(nums.begin() == --i) return ;

        for(;;) {
            i1 = i;
            if(*--i < *i1) {
                i2 = nums.end();
                while(!(*i < *--i2))
                    ;
                iter_swap(i, i2);
                reverse(i1, nums.end());
                //for(int i : nums) cout << i << " " ;
                return;
            }
        if(i == nums.begin()) {
            reverse(nums.begin(), nums.end());
            return ;
        }
        }
    }
};