0075. 颜色分类

题目链接

75. 颜色分类 - 力扣（LeetCode）

题目描述

给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数0、1和2分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

题目示例

示例 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的数组nums，要求原地排序，使得所有0在前，1在中，2在后。
   • 必须使用一趟扫描算法，且空间复杂度为O(1)。
2. 关键思路：
   • 双指针法：使用两个指针p0和p1分别跟踪0和1的插入位置。
   • 覆盖写入：遍历数组时，默认将当前元素置为2，然后根据原始值调整0和1的位置。
3. 算法流程：
   • 初始化p0和p1为0，表示0和1的插入起始位置。
   • 遍历数组：
     • 将当前元素nums[i]暂存为x，并将nums[i]置为2。
     • 如果x是0或1，将1写入p1位置，并右移p1。
     • 如果x是0，将0写入p0位置，并右移p0。
   • 最终0、1、2会按顺序排列。

题解代码

classSolution{publicvoidsortColors(int[]nums){intp0=0;// 指向0的插入位置intp1=0;// 指向1的插入位置for(inti=0;i<nums.length;i++){intx=nums[i];// 当前元素值nums[i]=2;// 默认将当前元素置为2if(x<=1){nums[p1]=1;// 如果x是0或1，将1放入p1位置p1++;// p1指针右移}if(x==0){nums[p0]=0;// 如果x是0，将0放入p0位置p0++;// p0指针右移}}}}

复杂度分析

1. 时间复杂度：
   • 仅遍历数组一次：O(n)。
2. 空间复杂度：
   • 仅使用常数空间（p0、p1、x变量）：O(1)。