首页
登录 | 注册

LeetCode: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,31,3,2
3,2,11,2,3
1,1,51,5,1


步骤如下:

  • 从最尾端开始往前寻找两个相邻的元素,两者满足i < ii(令第一个元素为i,第二个元素为ii)
  • 如果没有找到这样的一对元素则,表明当前的排列是最大的,没有下一个大的排列
  • 如果找到,再从末尾开始找出第一个大于i的元素,记为j                                  本文地址
  • 交换元素i, j,再将ii后面的所有元素颠倒排列(包括ii)
  • 如果某个排列没有比他大的下一个排列(即该排列是递减有序的),调用这个函数还是会把原排列翻转,即得到最小的排列
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int n = num.size();
        if(n == 1)return;
        for(int i = n-2, ii = n-1; i >= 0; i--,ii--)
            if(num[i] < num[ii])
            {
                int j = n-1;
                while(num[j] <= num[i])j--;//从尾部找到第一个比num[i]大的数,一定可以找到
                swap(num[i], num[j]);
                reverse(num.begin()+ii, num.end());
                return;
            }
        reverse(num.begin(), num.end());
    }
};

 

STL中还提供了一个prev_permutation,可以参考我的另一篇博客:here

 

【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3770126.html


相关文章

  • 前言:最近一直在刷leetcode的题,用到isalnum函数,用man手册查找了一下,总共有13个相关函数如下: #include <ctype.h> int isalnum(int c); int isalpha(int c ...
  • 前言:取得成功的要自律!可能有一腔热血,努力很长一阵子,但过一阵子之后,就不坚持了,所以要自律去约束自己时刻坚持着! 一.收获 8月份的收获还是很大的,主要有以下几个方面: 学会了使用github 注册账号很长时间了,但不怎么会用,这个月, ...
  • TensorFlow之DNN(三):神经网络的正则化方法(Dropout、L2正则化、早停和数据增强)
    这一篇博客整理用TensorFlow实现神经网络正则化的内容. 深层神经网络往往具有数十万乃至数百万的参数,可以进行非常复杂的特征变换,具有强大的学习能力,因此容易在训练集上过拟合.缓解神经网络的过拟合问题,一般有两种思路,一种是用正则化方 ...

2020 cecdns.com webmaster#cecdns.com
12 q. 0.068 s.
京ICP备10005923号