力扣(LeetCode)75. 颜色分类(C语言)

一、环境说明

1. 本文是 LeetCode 75题 : 颜色分类，使用c语言实现。
2. 双指针。
3. 测试环境:Visual Studio 2019。

二、代码展示

void swap(int *a,int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void sortColors(int* nums, int numsSize) {
    int p0 = 0, p2 = numsSize - 1;
    for (int i = 0; i < numsSize; i++) {
        //由于i和p0一路向右，不用担心p0的位置问题
        //但是p2一路向左，需要考虑：p2在i右边，可以交换，到i左边时，交换终止。否则i扫描到右边交换好的2时，又把它放在左面了。
        //p2和i可能同时指向2，交换后，p2向左一步,i向右一步，有一个2就被落在i前面了。所以要循环交换p2和i，直到i的位置不是2。
        while (i<=p2&&2 == nums[i]) {//2全部放在最后面,考虑交换后,nums[i]依然是2，继续交换
            swap(nums + p2, nums + i);
            p2--;
        }
        if (0 == nums[i]) {//0全部放在最前面
            swap(nums + p0, nums + i);
            p0++;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、思路分析

• 使用双指针:$p0$从前往后、$p2$从后往前。

1. 一次遍历$nums$，$i$表示当前位置，如果$nums[i]=0$，则交换$nums[i]$和$nums[p0]$。由于$i$和$p0$都是从左往右，这个交换方式是正确的。
2. 如果$nums[i]=2$，则交换$nums[i]$和$nums[p2]$。这个思路方向正确，但是有个小问题$:i$从左往右，$p2$从右往左。在交换时，可能$nums[p2]=nums[i]=2$，交换后，元素不变，但是$i$右移一位，有一个$2$就被落在$i$前面了。为了保证每一个$2$，都被放在数组最后，我们循环交换$nums[i]$和$nums[p2]$即可。

四、代码分析

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

五、AC

六、复杂度分析

1. 时间复杂度:$O(n)$ ,$n$是$nums$数组的大小。遍历$nums$的时间复杂度是$O(n)$，考虑到$p2$左移，最坏时间复杂度$O(2n)$，对应$nums$全$2$的情况
2. 空间复杂度:$O(1)$,除了若干变量使用的常量空间，没有额外使用线性空间。