题目描述

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

算法1

找规律 $O(n)$

C++ 代码

    // 从右往左，找到第一个index p，使得 x[p] < x[p+1], x[p]就是要被替换的数字
    // 在 x[p+1]..x[n-1]中找到比xs[p]大的最小的数字，与 x[i]交换，
    // 由于 x[p+1]..x[n-1]必然是单调递减的排序，所以从右向左遍历到第一个比x[p]大的数字，即为要交换的数字
    // 交换后，x[p+1]..x[n-1]依然是单调递减的序列，逆序，即得到最终结果。

    // 1 2 7 4 3 1 -> 1 2 [7 4 3 1] -> 1 3 [7 4 2 1] -> 1 3 1 2 4 7
    //                  p      q

    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if(n<=1) return;

        int p = -1;
        for(int i=n-2; i>=0; i--) {
            if(nums[i] < nums[i+1]) { p = i; break; }
        }

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

        for(int i=n-1; i>p; i--) {
            if(nums[i] > nums[p]) { swap(nums[i], nums[p]); break; }
        }

        reverse(begin(nums)+p+1, end(nums));
        return;
    }