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 条评论
登录 后参与评论

相关文章

来自专栏我的博客

C编程笔记

1.编译命令gcc test.c -o test 带上参数o就是指定编译文件名 2.printf(“%.2lf”,b) 其中前面2是小数点后位数,l是字母...

37250
来自专栏Petrichor的专栏

numpy: np.where

Note : 不接受 list 型的参数,只接受 `ndarray 型输入。

13730
来自专栏数据结构与算法

3038 3n+1问题

3038 3n+1问题  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 白银 Silver 题解 题目描述 Description 3n+...

36970
来自专栏我是业余自学C/C++的

原 三对角矩阵

15530
来自专栏desperate633

二维数组中的查找代码

9220
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之二维数组中的查找(九度OJ1384)

题目描述: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组...

23270
来自专栏Python爬虫实战

numpy基础操作快速入门

由于numpy不是python自带库,需要自己下载安装(如果用的是Anaconda,则不需要再去下载numpy库,因为其自带python环境以及许多第三方pyt...

8110
来自专栏Python小屋

Python版堆排序算法

其他排序算法的Python实现请参考:Python版归并排序算法(附Python程序__name__属性用法演示视频),侏儒排序算法原理与Python实现,Py...

35250
来自专栏ACM算法日常

字符串的距离(动态规划) - leetcode 72

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

8620
来自专栏前端儿

ASCII码排序

输入第一行输入一个数N,表示有N组测试数据。后面的N行输入多组数据,每组输入数据都是占一行,有三个字符组成,之间无空格。输出对于每组输入数据,输出一行,字符中间...

19220

扫码关注云+社区

领取腾讯云代金券