leetcode_next_permutation

发表于

难度：Medium

解题思路：
尝试了很多方法之后，终于找到一个正确的。从后往前看，你问我为什么这么看？因为越低位转换，改变值越小啊。

数组：[1,2,3,4,6,5,0]
要想找到比整数1234650大，且最邻近的数。从后往前看，最后三位650，怎么转换？没办法啊。
再往前看一位，4650，转换一下，有没有比它大数的可能产生，有啊6***、5***啊。
肯定是要替换掉4这个数字了，因为后面有比它大的数字。
至于用哪个替换，遍历一下后面数组，找到比它大、且最小的数字，跟它替换。
替换后要对后面的数组重新排序。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        auto reverse_it = nums.rbegin();
        for(;reverse_it != nums.rend() && reverse_it+1 != nums.rend(); reverse_it++)
        {
            if(*reverse_it > *(reverse_it+1))
            {
                auto switch_it = nums.rbegin();
                int switch_value = INT_MAX;
                for(auto it = nums.rbegin(); it != (reverse_it+1); it++)
                {
                    if(*it < switch_value && *it > *(reverse_it+1))
                    {
                        switch_it = it;
                        switch_value = *it;
                    }
                }
                swap(*switch_it, *(reverse_it+1));
                sort(nums.begin()+(nums.rend()-reverse_it)-1,nums.end());
                break;
            }
        }
        if(reverse_it == nums.rend() || reverse_it+1 == nums.rend())
        {
            sort(nums.begin(), nums.end());
        }
    }
};

代码如下:13ms,超过17.17%