75. 颜色分类

🟠   🔖  数组 双指针 排序  🔗 力扣 LeetCode

题目

Given an array nums with n objects colored red, white, or blue, sort them **in-place **so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

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

Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]

Output: [0,1,2]

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

题目大意

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

进阶：

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

解题思路

可以通过使用 荷兰国旗算法 来解决，这个算法是由 Edsger W. Dijkstra 提出的，核心思想是使用三指针来对数组进行分类。

1. 定义三个指针：

   • low 指针：用于追踪 0 的位置。
   • high 指针：用于追踪 2 的位置。
   • cur 指针：用于遍历数组。

2. 处理过程：

   • 遍历数组，使用 cur 指针。

   • 如果 cur 指向的元素是：

     • 0：将其与 low 位置的元素交换，然后移动 low 和 cur 指针。
     • 1：不做处理，直接移动 cur 指针。
     • 2：将其与 high 位置的元素交换，并将 high 指针左移（交换后 cur 指向的元素仍需要处理，因此不能移动 cur 指针）。

   • 完成遍历后，数组中的 0 将位于前面，1 位于中间，2 位于最后。

复杂度分析

• 时间复杂度：O(n)，数组只遍历了一次，每次迭代中执行常数次的交换或指针移动操作。
• 空间复杂度：O(1)，排序是原地进行的，使用了常量额外空间。

代码

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
	let cur = 0,
		low = 0,
		high = nums.length - 1;
	while (cur <= high) {
		if (nums[cur] == 0) {
			[nums[cur], nums[low]] = [nums[low], nums[cur]];
			cur++;
			low++;
		} else if (nums[cur] == 1) {
			cur++;
		} else {
			[nums[cur], nums[high]] = [nums[high], nums[cur]];
			high--;
		}
	}
};

相关题目

题号	标题	题解	标签	难度
148	排序链表	[✓]	链表 双指针 分治 2+
280	摆动排序 🔒		贪心 数组 排序
324	摆动排序 II		贪心 数组 分治 2+