31. Next Permutation

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 and use only constant 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函数。
那么，比如，对于序列

1, 2, 3

我们以人类的思维写一下字典序全排列

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

就可以总结出，求下一个排列的基本算法步骤是：

1. 从后向前扫描，找到改变升序趋势的拐点x，记下拐点位置pos
2. 再次从后向前扫描，找到第一个大于拐点的值y
3. 交换x, y的值
4. 将pos右边的序列反转

再举个具体的例子验证，比如序列

6, 8, 7, 4, 4, 3, 2

那么，
1. 找到拐点6， 因为从后向前扫描时，8, 7, 4, 4, 3, 2是一个升序趋势序列，而本例中，6改变了这个趋势，6的pos是0
2. 再次从后向前扫描，找到第一个大于拐点的值y， 显然，本例中是7
3. 交换6，7的值，序列就变成了 7, 8, 6, 4, 4, 3, 2
4. 将pos右边的序列反转，得到结果 7, 2, 3, 4, 4, 6, 8

剩下的就是写出代码

code

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

        for (int i = nums.size() - 2; i >= 0; --i) {
            if (nums[i] >= nums[i + 1]) continue; 

            for (int j = nums.size() - 1; j > i; --j) {
                if (nums[j] > nums[i]) {
                    swap(nums[j], nums[i]);
                    reverse(nums.begin() + i + 1, nums.end());
                    return;
                }
            }  
        }

        reverse(nums.begin(), nums.end());        
    }
};