Leetcode 31 Next Permutation

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

找到字典序的下一个排列.

偷懒做法

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(next_permutation(nums.begin(),nums.end())) return;
        sort(nums.begin(),nums.end());
    }
};

当然本着小题大做的原则,肯定不能这样放松要求哇。

算法原理查看 http://blog.csdn.net/accepthjp/article/details/52432954

找出从最右向左最长递增序列的左边一个元素,将最长递增序列逆置,这样得到的是该序列的最小字典序排列,再将找到的左边一个元素和该序列中大于它的最小一个元素交换位置。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 27 Remove Element

    Given an array and a value, remove all instances of that value in place and ret...

    triplebee
  • Leetcode 26 Remove Duplicates from Sorted Array

    Given a sorted array, remove the duplicates in place such that each element app...

    triplebee
  • Leetcode 80 Remove Duplicates from Sorted Array II

    Follow up for "Remove Duplicates": What if duplicates are allowed at most twic...

    triplebee
  • LeetCode 697. 数组的度

    给定一个非空且只包含非负数的整数数组 nums 数组的度的定义是指数组里任一元素出现频数的最大值

    Michael阿明
  • leetcode之移动零

    这里遍历数组,维护一个下标,当值不为0时则进行移动同时递增下标,遍历完一次之后,在从该下标起往后遍历,赋值为0。

    codecraft
  • leetcode之移动零

    这里遍历数组,维护一个下标,当值不为0时则进行移动同时递增下标,遍历完一次之后,在从该下标起往后遍历,赋值为0。

    codecraft
  • Array - 80. Remove Duplicates from Sorted Array II

    80、Remove Duplicates from Sorted Array II 相似题型: 26

    用户5705150
  • 算法leetcode-15

    opprash
  • 关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2

    题目 Leetcode 217. Contains Duplicate Given an array of integers, find if the arra...

    WZEARW
  • 283 Move Zeroes

    /** * 题意:将0挪到末尾,并且不改数组中原有元素的顺序 * 解析:找到0元素,然后寻找其后面非0的元素,进行交换位置 * @param {numbe...

    用户1624346

扫码关注云+社区

领取腾讯云代金券