31. Next Permutation

31. Next Permutation

题目意思解释: 比如有[9, 5, 6, 4, 1],代表一个数95641，要找到通过数列中数字组合而成的大于这个数中的最小一个，即96145, [9, 6, 1, 4, 5]

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int turningPoint = 0;
        int justGreater = 0;
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] > nums[i - 1])
            {
                turningPoint = i;
                justGreater = i;
            }else if(turningPoint && nums[i] > nums[turningPoint - 1])
                justGreater = i;       
        }
        if(turningPoint)
            swap(nums[justGreater], nums[turningPoint - 1]);
        reverse(nums, turningPoint);
    }
private:
    void reverse(vector<int>& nums, int start)
    {
        int end = nums.size() - 1;
        while(start < end)
            swap(nums[start++], nums[end--]);
    }
};

要注意到转折点后的序列必然是递减的

寻找序列中第一个满足a[i] > a[i - 1]且其后序列递减的一部分作为转折点，将a[i - 1]和后面递减序列中刚刚好大于a[i - 1]的数a[j]交换，因为a[j - 1] > a[j]其a[j + 1] < a[j]，而a[i - 1] < a[j] && a[i - 1] > a[j + 1]，所以交换后后面的递减次序不变，为了实现最小，只需要将交换后的后面再升序排列即可。

review

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int turningPoint = -1;
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] > nums[i - 1])
                turningPoint = i;
        }
        if(turningPoint == -1)
        {
            sort(nums.begin(), nums.end());
        }else
        {
            sort(nums.begin() + turningPoint, nums.end());
            auto num = upper_bound(nums.begin() + turningPoint, nums.end(), nums[turningPoint - 1]);
            swap(*num, nums[turningPoint - 1]);
        }
    }
};