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, 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

分析及题解:这道题是寻找给定的一列数的下一个排列, 如果给定的数是该列数的最后一个排列, 则该列数的下一个排列是该列数的第一个排列. 如6, 5, 4, 3, 2, 1是该列数的最后一个排列, 则下一个排列是1, 2, 3, 4, 5, 6, 也即是该列数的第一个排列.

解决这道题的重点是找到排列数的下一个排列数的生成规律, 对于1, 2, 6, 5, 4, 3的下一个排列数为1, 3, 2, 4, 5, 6. 规律如下:

从后往前寻找第一个从后往前不是递增的数, 用index指向它, 此处是2, 即index = 1, 因为2小于6, 不满足从后往前递增. 然后从后往前寻找第一个大于index指向的数, 用p指向该数, 此处为3, 即p = 5. 交换index和p指向的数, 最后将index后的数逆序即可. 如果找到的index为0, 则直接逆序整个数列即可. 整个过程中需要三次遍历, 算法复杂度是O(3n)即O(n).

过程如下:

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

代码:

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size() < 2) return;
        
        int index = nums.size() - 2;
        while(index > 0 && nums[index] >= nums[index+1]) {
            // 找到第一个从后往前数不是递增序的数
            index--;
        }
        
        int p = nums.size() - 1;
        while(p > index && nums[p] <= nums[index]) {
            // 从后往前找到第一个大于index所指的数
            p--;
        }
        
        int tmp;
        if(p != index) { // nums不是最后一个排列
            // 交换p和index所指向的数据
            tmp = nums[p];
            nums[p] = nums[index];
            nums[index] = tmp;
            index++;
        }
        // 逆序index之后的数
        p = nums.size() - 1;
        while(index < p) {
            tmp = nums[index];
            nums[index] = nums[p];
            nums[p] = tmp;
            index++;
            p--;
        }
    }
};