双指针

LeetCode31.下一个排列

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

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

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

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), i = n - 2, j = n - 1, k = n - 1;

        while (i >= 0 && nums[i] >= nums[j]) i -- , j -- ;  //从后往前找第一个升序对

        if (i >= 0) 
        {
            while (nums[i] >= nums[k]) k -- ;     //再从后往前找第一个大于nums[i]的数
            swap(nums[i], nums[k]);               //交换这两个数,并将i后面的数按升序排序
        }

        sort(nums.begin() + j, nums.end());
    }
};


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×