Code & Func

打卡，第17天

恩，又是一道有趣的题目，不知不觉刷了12道Medium级别的题目了，要不要找个时间试试hard的？？

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

我们再观察几个示例：

1,2,5,4,3 -> 1,3,2,4,5 1,3,2,5,4 -> 1,3,4,2,5

我们的目的是：让这个序列变大一点，显然从后向前考虑会比较容易得出结果。

对于1,2,5,4,3，观察序列的最后，我们可以发现4,3是降序的，我们要让整个序列变得大一点，显然如果只修改对于5,4,3这个序列的顺序，我们是没法让整个序列变大的，所以我们要引入下一个数字，但是5,4,3也是降序的，所以我们也无法只修改后三个数字来是的序列变大，但是如果考虑2,5,4,3，这个序列再变大一点就是3,2,4,5,如果多试几次的话，就可以找出规律了：

我们从后向前找一个最长升序序列nums[i:]
如果i=0，按照题目要求，我们就应该给出一个最小的组合，就直接对nums进行排序即可。
如果i!=0，那么我们从后向前找第一个比nums[i-1]大的数字nums[k]，而且我们肯定能找出。交换nums[i-1]和nums[k],然后再对nums[i:]进行一个排序即可。

1
void nextPermutation(vector<int>& nums) {
2
    for(int i = nums.size() - 1;i > 0;i--){
3
        if (nums[i-1] < nums[i]){
4
            int key = nums[i -1];
5
            int j;
6
            for(j = i;j < nums.size() && nums[j] > key;j++)
7
                /*do nothing*/;
8
            cout << nums[j-1] <<" " << nums[i-1];
9
            swap(nums[j-1],nums[i-1]);
10
            sort(nums.begin() + i,nums.end());
11
            return ;
12
        }
13
    }
14
    sort(nums.begin(),nums.end());
15
}

这样的话，时间复杂度是O(nlogn)了。其实我们要排序的序列，在某种程度上来说，他其实是降序的，我们只需要把降序换成升序即可。

1
void nextPermutation(vector<int>& nums) {
2
    int i,j = -1;
3
    for(i = nums.size() - 1;i > 0 && nums[i-1]>= nums[i] ;i--)
4
        /*do nothing*/;
5

6
    int first = i,last = nums.size()-1;
7

8
    while(first <= last) {
9
        if (i > 0 && nums[last] > nums[i-1]) {
10
            swap(nums[i-1],nums[last]);
11
            break;
12
        } else if (i > 0 && nums[first+1] <= nums[i-1] ) {
13
            swap(nums[i-1],nums[first]);
14
            break;
15
        }
6 collapsed lines
16
        swap(nums[first++],nums[last--]);
17
    }
18
    while(first < last)
19
        swap(nums[first++],nums[last--]);
20
    return ;
21
}

还可以先对nums[i:]进行reverse,在找出第一个比nums[i-1]大的数和nums[i-1]进行交换。

1
void nextPermutation(vector<int>& nums) {
2
    if (nums.size() < 2) return ;
3
    int i,j = -1;
4
    for(i = nums.size() - 1;i > 0 && nums[i-1]>= nums[i] ;i--)
5
        /*do nothing*/;
6

7
    int first = i,last = nums.size()-1;
8
    while(first < last)
9
        swap(nums[first++],nums[last--]);
10
    //cout << i << endl;
11
    if (i > 0) {
12
        auto beg = nums.begin() + i;
13
        auto it = lower_bound(beg,nums.end(),nums[i-1]);
14
        //cout << *it << endl;
15
        while (*it == nums[i-1])
6 collapsed lines
16
            it++;
17
        //cout << *it << nums[i-1] << endl;
18
        swap(*it,nums[i-1]);
19
    }
20
    return ;
21
}

由于dicuss中的都大同小异，所以就不贴dicuss中的算法了。