本文共 989 字，大约阅读时间需要 3 分钟。

链接

耗时

解题：4 h 45 min

题意

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

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

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

思路

实现 C++ 的 next_permutation() 。

从后向前找到第一个非逆序的数字 nums[i]，然后在 [i+1,n-1] 里面找大于 nums[i] 的最小的数字 nums[pos]，交换 nums[i] 和 nums[pos]，然后将 [i+1,n-1] 区间的数字从小到大排序。

如果不存在非逆序的数字，说明不存在下一个更大的排列，直接翻转 nums[] 。

时间复杂度：$O(nlogn)$

AC代码

class Solution {   public:    void nextPermutation(vector
   
    & nums) {           int n = nums.size();        if(n <= 1) return ;        for(int i = n-2; i >= 0; --i) {               if(nums[i] >= nums[i+1]) continue;            int tmp = INT_MAX, pos = i;            for(int j = i+1; j < n; ++j) {                   if(nums[j] > nums[i] && nums[j] < tmp) {                       tmp = nums[j];                    pos = j;                }             }            swap(nums[pos], nums[i]);            sort(nums.begin()+i+1, nums.end());            return ;        }        reverse(nums.begin(), nums.end());    }};