75. 颜色分类 (opens new window)

Description

Difficulty: 中等

Related Topics: 数组 (opens new window), 双指针 (opens new window), 排序 (opens new window)

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

进阶：

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

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {void}
 * 
 */
// 当前数为0，就往前放，放了之后0指针自然就+1;
// 但还需要cur也加1，因为cur已经为0了，交换后，不可能变大，所以curr也得往前
// 这里start不能++，因为后面交换回来的，有可能是0，所以还得经下一轮比较判断，再决定是否+1
// 为1，就是特殊情况，暂时不动，继续往前查找
var sortColors = function(nums) {
    let [i, l, r] = [0, 0, nums.length - 1];
    
    while (i <= r) {
        if (!nums[i]) [nums[i++], nums[l++]] = [nums[l], nums[i]];
        else if (nums[i] === 2) [nums[i], nums[r--]] = [nums[r], nums[i]];        
        else i++;                                    
    }                        
};