【leetcode】31. 下一个排列（next-permutation）（模拟）[中等]

链接

https://leetcode-cn.com/problems/next-permutation/

耗时

解题：4 h 45 min
题解：13 min

题意

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

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

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

思路

实现 C++ 的 next_permutation() 。

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

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

时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)

AC代码

class Solution {
public:
    void nextPermutation(vector<int>& 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());
    }
};