leetcode 31. 下一个排列(Next Permutation)

佚名 6年前 (2019-04-12) 随笔 1941人围观抢沙发百度已收录

题目描述：

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解法：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        // 1 7 8 6 5
        // 1 5 8 7 6
        int sz = nums.size();
        if(sz <= 1){
            return;
        }else{
            int i = sz-2;
            while(i >= 0 && nums[i] >= nums[i+1]){
                i--;
            }
            int l = 0, r = 0;
            if(i < 0){
                l = 0;
                r = sz-1;
                while(l < r){
                    swap(nums[l++], nums[r--]);
                }
            }else{
                // should increase nums[i]
                r = sz-1;
                while(nums[r] <= nums[i]){
                    r--;
                }
                swap(nums[r], nums[i]);
                // reverse the right part starting from i+1 element
                l = i+1;
                r = sz-1;
                while(l < r){
                    swap(nums[l++], nums[r--]);
                }
            }
        }
    }
};