75. [✔][M]颜色分类

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

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

---

题解：

思路

这道题可以使用荷兰国旗问题的思路来解决。 荷兰国旗问题是指：有一个数组，包含 3 种颜色的球（红、白、蓝），要求将这些球按照颜色顺序（红、白、蓝）排序。

思路：

我们可以设置 3 个指针，一个指向头部，一个指向尾部，还有一个指向当前遍历的元素。 我们从头部开始遍历数组，如果遇到 0（红色）就把它放到头部指针的位置，如果遇到 2（蓝色）就把它放到尾部指针的位置。 如果遇到 1（白色），就跳过它，继续遍历。

复杂度 时间复杂度:

O(n) , 因为双指针指针最多向右移动 n 次。

空间复杂度:

O(1)

// @lc code=start
/**
 Do not return anything, modify nums in-place instead.
 */
function sortColors(nums: number[]): void {
    let left = 0;
    let right = nums.length - 1;

    const swap = (nums, x, y) => {
        [nums[x], nums[y]] = [nums[y], nums[x]];
    }

    for (let i = 0; i <= right; i++) {
        if (nums[i] === 0) {
            swap(nums, i, left);
            left++;
        } else if (nums[i] === 2) {
            swap(nums, i, right);
            right--;
            i--;
        } else if (nums[i] === 1) {
        }
    }
};
// @lc code=end