即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

【LeetCode】 31. Next Permutation

编程语言 xiazhiyiyun 18℃ 0评论
本文目录
[隐藏]

1.【LeetCode】 31. Next Permutation

1.1.介绍

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

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

题意:


实现“下一个排列”函数,将排列中的数字重新排列成字典序中的下一个更大的排列。如果这样的重新排列是不可能的,它必须重新排列为可能的最低顺序(即升序排序)。重排必须在原地,不分配额外的内存。

1.2.解答

考虑序列4,3,2,1,显然对于此序列中并不存在比其更大的,因为此序列中是降序排列的,是此数字全排列的最大值。

考虑6 2 4 8 7 5 1,其下一个序列应该是6 2 5 1 4 7 8

其步骤应该如下:


1. n>0且n

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size()-1;
        int left,right;

        //步骤1:寻找 nums[n-1] >= nums[n]
        while(n > 0 && nums[n-1] >= nums[n])
            --n;

        if(n>0)
        {
            int index = n-1;
            //步骤2:n-1是大于nums[index]的最小值
            while(n < nums.size() && nums[index] < nums[n])
                ++n;
            //步骤3:交换
            swap(nums[index],nums[n-1]);
            left = index+1;
        }else   left = 0;

        right = nums.size()-1;
        while(left < right)
            swap(nums[left++],nums[right--]);
        return;

    }
};

转载请注明:CodingBlog » 【LeetCode】 31. Next Permutation

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情