企业官网建设流程全解析

题目概览

给定一个包含红色、白色和蓝色、共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]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i]为0、1或2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

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

解题分析

方法：双指针

定义两个指针 a 和 b，a 负责 0 的交换，b 负责 1 的交换，则：

1. b 指针的位置一定小于等于 a，令 a、b 初始值都为 0；
2. 当当前元素为 0 时，与 a 进行交换，a++；
   若此时 b 小于 a，b++；
   若交换后的元素为 1，与 b 进行交换，b++；
3. 当当前元素为 1 时，与 b 进行交换，b++；

时间复杂度：O(n)
空间复杂度：O(1)

class Solution { public void sortColors(int[] nums) { int a = 0, b = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) { swap(nums, a, i); a++; if (b < a) { b++; } } if (nums[i] == 1) { swap(nums, b, i); b++; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }