Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Next Permutation

Leetcode algorithms 第 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

解答

STL直接有next_permutation的函数可以调用,其思想也比较直接。因为按升序排序是最小的,按降序排序是最大的,对于一个排列,从后往前找到第一个数x,其小于后面相邻的数字,再从后往前找到第一个数字y,其大于x,交换x跟y,然后把原先x后面的数字逆置,即可得到下一个排列。

比如原排列为1 3 5 4 2,找到第一个数3,其小于后面的数字5,然后找到第一个数字4,其大于3,交换3和4,得到1 4 5 3 2,然后逆转原来3后面的数字,即5 3 2,得到1 4 2 3 5,即为下一个排列。

具体代码如下:

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if (num.size() == 1) return;
        
        int i = num.size() - 2;
        while(i >= 0 && num[i]>= num[i+1]) i--; //找第一组升序
        
        if (i == -1) //全部降序,已是最大排列
        {
            reverse(num.begin(), num.end());
            return;
        }
        
        int j = num.size() - 1; //找第一个大于num[i]的
        while (num[i] >= num[j]) j--;
        swap(num[i], num[j]); //交换
        
        reverse(num.begin() + i + 1, num.end()); //逆转
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论