力扣第 75 题是 颜色分类

题目描述

输入：一个数组 nums，其中元素只能是 0、1 和 2。

输出：对数组进行排序，使其按顺序排列。

你需要使用 原地算法，即不能使用额外的空间来完成排序。

示例

示例 1

输入：

nums = [2, 0, 2, 1, 1, 0]

输出：

[0, 0, 1, 1, 2, 2]

示例 2

输入：

nums = [2, 0, 1]

输出：

[0, 1, 2]

解题思路

1. 计数排序

• 遍历数组，统计 0、1、2 的个数。
• 然后按照统计的数量依次将 0、1、2 填回数组。

这种方法需要两次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

2. 双指针法

使用三个指针：

• p0：指向下一个应该放置 0 的位置。
• p2：指向下一个应该放置 2 的位置。
• curr：用于遍历数组。

算法过程：

1. 初始化 p0 = 0，curr = 0，p2 = n - 1。
2. 遍历数组：
   • 如果 nums[curr] == 0：将 nums[curr] 与 nums[p0] 交换，p0++，curr++。
   • 如果 nums[curr] == 2：将 nums[curr] 与 nums[p2] 交换，p2--，但此时 curr 不前进（因为交换过来的元素还需要检查）。
   • 如果 nums[curr] == 1：curr++。

这种方法只需一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

实现代码

双指针法实现

#include <stdio.h>

void sortColors(int* nums, int numsSize) {
    int p0 = 0, curr = 0, p2 = numsSize - 1;

    while (curr <= p2) {
        if (nums[curr] == 0) {
            // 交换 nums[curr] 和 nums[p0]
            int temp = nums[curr];
            nums[curr] = nums[p0];
            nums[p0] = temp;
            p0++;
            curr++;
        } else if (nums[curr] == 2) {
            // 交换 nums[curr] 和 nums[p2]
            int temp = nums[curr];
            nums[curr] = nums[p2];
            nums[p2] = temp;
            p2--;
        } else {
            curr++;
        }
    }
}

int main() {
    int nums[] = {2, 0, 2, 1, 1, 0};
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    sortColors(nums, numsSize);

    // 输出排序后的数组
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

代码解析

1. 变量初始化：

   • p0 指向当前应该放 0 的位置。
   • p2 指向当前应该放 2 的位置。
   • curr 遍历数组。

2. 循环逻辑：

   • 如果 nums[curr] == 0：
     • 交换 nums[curr] 和 nums[p0]。
     • 更新 p0 和 curr。
   • 如果 nums[curr] == 2：
     • 交换 nums[curr] 和 nums[p2]。
     • 更新 p2。
   • 如果 nums[curr] == 1：
     • 直接更新 curr。

3. 结束条件：

   • 当 curr > p2 时，所有元素已经按要求排序。

时间复杂度和空间复杂度

• 时间复杂度：

  • 只需一次遍历，时间复杂度为 O(n)。

• 空间复杂度：

  • 没有使用额外的空间，空间复杂度为 O(1)。