LeetCode 31. Next Permutation

31. Next Permutation

Difficulty: medium

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 and use only constant 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 Cheat Version:

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

Rate:
Runtime: 4 ms, faster than 98.80% of C++ online submissions for Next Permutation.
Memory Usage: 8.7 MB, less than 79.57% of C++ online submissions for Next Permutation.

尝试了一下直接使用标准模板算法库中提供的next_permutation, 发现也是给过的.

但毕竟秉着尊重算法的精神, 手搓还是要想办法手搓一遍的.
但关键是, 在看到直接调用STL函数给出的Rate只有80%的时候, 写这题的目的也就改变了哈哈–干翻STL.

参考了cppreference提供的next_permutation的实现版本, 写出了以下的代码:

Build Version:

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        switch (nums.size()) {
            case 2:
                reverse(nums.begin(), nums.end());
            case 0: case 1:
                return ;
        }
        auto isInversion = is_sorted(nums.begin(), nums.end(), greater<int>());
        if (isInversion) {
            reverse(nums.begin(), nums.end());
            return ;
        }
        
        auto i = nums.end() - 1;
        while (true) {
            vector<int>::iterator i1, i2;
            
            i1 = i;
            if (*--i < *i1) {
                i2 = nums.end();
                while (*--i2 <= *i)
                    continue;
                iter_swap(i, i2);
                reverse(i1, nums.end());
                break;
            }
        }
    }
};

Rate:
Runtime: 8 ms, faster than 74.87% of C++ online submissions for Next Permutation.
Memory Usage: 8.7 MB, less than 75.27% of C++ online submissions for Next Permutation.

get到了比刚才更慢的速度, 同样的内存. 干翻STL计划失败.

思路大致是, 从后往前找到倒数第一对前一个数比后一个数小的位置(满足这种情况的时候, 该位置之后的所有元素一定满足前一个数比后一个数小, 也就是最后一个数一定是这些数里面最小的), 然后从后再找一个比这个较小数大一点的数与他交换(刚才的括号已经说明了这后面的元素都是小于号顺序的, 所以从后往前找到的一定是最接近的那一个), 在将后面的顺序序列逆序, 将顺序的方向改变.

这段话, 我估摸着下次应该就看不懂了.