描述 Description

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.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

[Next Permutation]

分析 Analysis

算法过程如下图所示：从右到左找到一个上升序列23478，刚要下降的那个数如6和上升序列中的刚好比6大一点的7交换，再将7后面的上升序列倒序。[http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html]

代码 Code

class Solution {
    void nextPermutation(vector<int>& nums) {
        int k = -1;
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                k = i;
                break;
            }
        } 
        if (k == -1) {
            reverse(nums.begin(), nums.end());
            return;
        }
        int l = -1;
        for (int i = nums.size() - 1; i > k; i--) {
            if (nums[i] > nums[k]) {
                l = i;
                break;
            } 
        } 
        swap(nums[k], nums[l]);
        reverse(nums.begin() + k + 1, nums.end()); 
    }
};

    bool next_permutation(vector<int> &nums, int begin, int end) {
        // From right to left, find the first digit(partitionNumber) 
        // which violates the increase trend
        int p = end - 2;
        while (p > -1 && nums[p] >= nums[p + 1]) --p;

        if(p == -1) {
            reverse(&nums[begin], &nums[end]);
            return false;
        }

        int c = end - 1;
        while (c > 0 && nums[c] <= nums[p]) --c;

        swap(nums[p], nums[c]);
        reverse(&nums[p+1], &nums[end]);
        return true;
    }