leetcode 31 Next Permutation

mplement 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.

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

本题其实是考你全排列怎么生成，具体就是stl里的next_permutation() 的实现，类似的我们还可以问pre_permutation()怎么实现(就是符号换一下)，具体参考stl源码解析。

class Solution {
public:
    void nextPermutation(vector<int>& nums) 
    {
        if(nums.size() <= 1) return;
        vector<int>::iterator first = nums.begin();
        vector<int>::iterator last = nums.end();

        int count = nums.size() - 1;//找合适couple的最大次数

        vector<int>::iterator i = last - 2;
        vector<int>::iterator ii = last - 1;
        while(count > 0)
        {
            if ((*i) < (*ii))
            {
                break;
            }
            else
            {
                i--;
                ii--;
                count--;
            }
        }

        if (count == 0) //整个序列已经没有更大的了，需要返回最小的
        {
            reverse(first, last);
        }
        else
        {
            vector<int>::iterator j = last - 1;
            while( (*j) <= (*i) ) j--;

            int temp = (*j);//交换i， j
            (*j)=(*i);
            (*i)=temp;
            
            reverse(ii, last);
        }

    }
};