Sitch's Blog
0%

LeetCode-No-31

发表于 分类于 Valine：

下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

思路分析

①是否存在更大的排列

更大的排列

考虑最大的字典序排列: 降序排列 [1,2,3] → [3,2,1] 对于 [3,2,1] 序列,已经是最大字典序了

假如序列存在一个更大的排列,那它必然不是降序排列 因此判断是否存在下一个排列的条件就是 顺序遍历数组,判断是否完全降序

②找到下一个排列

首先对于[1,2,3,4,5,6],假如我们要人工找到下一个排列,我们知道要把倒数两位调换一下[1,2,3,4,6,5],这样值的变动最小,字典序大小变动也最小.

为什么最后两位调换之后字典序会变大呢?

我们可以发现一个本质: 它们是升序的, 升序排列那么必然就存在可以调换成降序的操作空间,因此可以改动升序关系的任意两位来获取一个更大的字典序 如 [1,2,5,4,3,6]

知道了获得更大序的方法,接下来我们要确定什么操作能得到最小的更大序(下一个更大的序列)

其实字典序类似于数的大小关系. 比如[1,2,3] → [2,1,3][1.3.2]

所以为了找到最小的更大序列,我们操作的升序数对要尽可能的小.所以目标就变成了:

找到最靠后的一对升序数对

[9,8,3,6,5,4]→[9,8,4,3,5,6] 最靠后的/最小的 升序数对是 [3,4],初步调换后是[9,8,4,6,5,3] 显然这个结果还不太对.

找到了最小的升序数对只是保证了在一步操作的范围内,我们增加的值是最小的. 换句话说,其实再多加几步操作才能保证是下一个序列. 来看看我们还差些什么 [9,8,4,6,5,3] →[9,8,4,3,5,6] , 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
    void nextPermutation(vector<int& nums) 
    {
        if(nums.size()<=1)
            return ;
        
        int flag=0;
        int nextid=nums.size()-1;
        int currentid=nextid-1;
        
        while(currentid=0)
        {
            if(nums[nextid]nums[currentid])
            {   
                //从后往前，找到第一组 升序对
               flag=1;
                break;
            }
            
            nextid--;
            currentid--;
        }
        
        if(flag==1)//存在下一个更大排列
        {
                //交换生成新排列
            while(nextid+1<nums.size())
            {
                if(nums[nextid+1]nums[currentid] )
                    nextid++;
                else
                    break;
            }
            tempswap(nums[currentid],nums[nextid]);
            //currentid右边必然是降序
            //将currentid右边升序处理
            nextid=nums.size()-1;
            while(currentid+1<nextid)
            {
                tempswap(nums[nextid],nums[currentid+1]);
                nextid--;
                currentid++;
            }
        }   
        else
        {   //不存在，则倒序
            nextid=nums.size()-1;
            currentid=0;
            while(currentid<nextid)
            {
                tempswap(nums[nextid],nums[currentid]);
                nextid--;
                currentid++;
            }
            
        }
        
        return ;
        
        
        
    }
    
    void tempswap(int& a,int& b)
    {
        int temp=b;
            b=a;
            a=temp;
    }
};