力扣(LeetCode)31. 下一个排列(C语言)

一、环境说明

1. 本文是 LeetCode 31题 : 下一个排列，使用c语言实现。
2. 重在排列性质。
3. 测试环境:Visual Studio 2019。

二、代码展示

//找下一个排列！
void swap(int *a,int *b){//交换
    int temp = *a;
    *a = *b;
    *b = temp;
}
void reverse(int nums[],int left,int right){//反转
    while(left<right){
        swap(nums+left,nums+right);
        left++,right--;
    }
}
void nextPermutation(int* nums, int numsSize){
    int i = numsSize - 2;
    while(i>-1&&nums[i]>=nums[i+1]){//i在nums内,nums[i]>=nums[i+1]
        i--;//从右往左遍历
    }
    //此时nums[i]是第一个小于nums[i+1]的数
    int j = numsSize -1;
    if(i>-1){//如果nums已经降序排列，i是-1，走不到这一步。
        while(j>-1&&nums[i]>=nums[j]){//不考虑重复元素。//看上一行，不会越界的。
            j--;
        }
        //此时nums[j]是第一个大于nums[i]的数。
        swap(nums+i,nums+j);
    }
    reverse(nums,i+1,numsSize-1);//反转nums[i]右边的所有数
}
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

三、思路分析

• 下一个排列，字典序更大。如果组成整数，下一个排列，是第一个数值大于当前排列的排列。
• 所以我们的目的具现为：找到第一个数值大于当前排列的排列。
• 为了找到上述排列。我们需要：

1. 从右往左遍历，当前位置是$i$。
2. 当$nums[i]<nums[i+1]$，选定$nums+i$作为需要被交换的数。这一步确保$nums[i]$右侧是一个降序序列。
3. 再次从右往左遍历$nums$，当前位置是$j$,当$nums[j]>nums[i]$,选取$nums+j$作为被交换的第二个数。
4. 由于$2$的操作，$nums[i]$右侧的排列，是右侧的最大排列。反转$nums[i]$右边所有数字，得到$nums[i]$右侧的最小排列。

• 找到了~下一个排列！

四、代码分析

• 理解思路很重要！
• 欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

1. 时间复杂度:$O(n)$ ,$n$是$nums$的大小，二次遍历$nums$的时间复杂度是$O(n)$。
2. 空间复杂度:$O(1)$,除若干变量使用的常量空间，没有额外使用线性空间。