Leetcode-31:Next Permutation

2018-01-16

问题描述：

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

我的答案

//从后找，找到第一个非倒序aZXY,将第一个比a大的与a置换，剩余升序，YaXZ
void nextPermutation(vector<int>& nums) {
    bool changed = false;
    int temp;
    int change;
    if(nums.size()>1){
        vector<int>::iterator it = nums.begin();
        temp = nums.back();
        int i = nums.size()-2;
        for (i; i>-1; i--) {
            if (temp>nums[i]) {
                change = i+1;
                while (change<nums.size()&&nums[i]<nums[change]) {
                    change++;
                }
                change--;
                swap(nums[change], nums[i]);
                for (int k=i; k>=0; k--) {
                    it++;
                }
                sort(it, nums.end());
                //跳出循环，同时与找不到而跳出循环有所标记
                i = -2;
            }else{
                temp = nums[i];
            }
        }
        if(i==-1){
            sort(nums.begin(), nums.end());
        }
    }
}

其他高效答案

void nextPermutation(vector<int>& nums) {
        int len = nums.size(), flag = 1, index = len - 1;
        for (int i = len - 1; i>0; i--){
            if (nums[i] <= nums[i - 1]) index--;
            else{
                for (int j = len - 1; j >= index; j--){
                    if (nums[j]>nums[i - 1]){
                        swap(nums[i - 1], nums[j]);
                        break;
                    }
                }
                sort(nums.begin() + i , nums.end());
                flag = 0;
                break;
            }
        }
        if (len&&flag) sort(nums.begin(), nums.end());
    }