美文网首页
leetcode31.下一个排列

leetcode31.下一个排列

作者: 今天不想掉头发 | 来源:发表于2019-09-26 18:49 被阅读0次
    image.png

    返回数组的下一个字典序,解决思路:
    从后往前找,找到一个a[i - 1],使得a[i - 1] < a[i],然后从a[i]向后找,找到一个最接近a[i - 1]且大于a[i - 1]的数a[j],交换a[i - 1]和a[j],此时a[i - 1]后面的序列还是递减的,将a[i - 1]后面的序列翻转,即是我们想要的结果。

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int i = nums.size() - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }
            if (i >= 0) {
                int j = nums.size() - 1;
                while (j >= 0 && nums[i] >= nums[j]) {
                    j--;
                }
                swap(nums[i], nums[j]);
            }
            reverse(nums.begin() + (i + 1), nums.end());
        }
    };
    

    相关文章

      网友评论

          本文标题:leetcode31.下一个排列

          本文链接:https://www.haomeiwen.com/subject/phusyctx.html