题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

样例

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

算法1

(算是模拟？) $O(n)$

从右往左，找到递减的点(如果整个数组都没找到，那说明已经是最大的那种排列了)；
在递减点右边找到大于它的最小值，交换两者，然后右边reverse一下即可；

举例 [1, 3, 5, 4, 2];
递减点为5->3，在3的右边找到大于它的最小值，即4，交换它们，得[1, 4, 5, 3, 2];
将4右边得数reverse即可，得[1, 4, 2, 3, 5].

时间复杂度

线性扫描找递减点，$O(n)$;
找大于递减点得最小值，$O(logn)$;
翻转$O(n)$;
所以总时间复杂度$O(n)$。

参考文献

C++ 代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.empty()) return;
        int n = nums.size();
        int i = n - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) --i;
        if (i < 0) {
            reverse(nums.begin(), nums.end());
            return;
        }

        int l = i + 1, r = n - 1, target = nums[i];
        while (l <= r){
            int mid = l + (r - l) / 2;
            if (nums[mid] <= target) r = mid - 1;
            else l = mid + 1;
        }

        swap(nums[i], nums[r]);
        reverse(nums.begin() + i + 1, nums.end());
    }
};