题目描述补充

题目：颜色分类

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

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

注意：你不能使用额外的数组空间，并且你只能在原地对数组进行排序，也就是说，你只能修改输入数组。

示例

输入：[2, 0, 2, 1, 1, 0] 输出：[0, 0, 1, 1, 2, 2]

解题思路

可以使用三指针法来解决这个问题。我们设置三个指针：

• p0 指向当前已经排好序的 0 的最后一个位置（初始化为0，因为数组可能从索引0开始就是0）。
• curr 遍历数组的当前位置（初始化为0）。
• p2 指向当前尚未处理的元素中第一个 2 的位置（初始化为数组长度-1，因为数组末尾可能是2）。

遍历数组，根据当前元素的值进行如下操作：

• 如果 nums[curr] == 0，则与 nums[p0] 交换，并同时递增 p0 和 curr。
• 如果 nums[curr] == 1，则只递增 curr。
• 如果 nums[curr] == 2，则与 nums[p2] 交换，但只递减 p2（因为交换过来的元素未知，curr 需要保持不变以重新检查新交换来的元素）。

示例代码

PHP

function sortColors(&$nums) {
    $p0 = 0;
    $p2 = count($nums) - 1;
    $curr = 0;

    while ($curr <= $p2) {
        if ($nums[$curr] == 0) {
            list($nums[$curr], $nums[$p0]) = array($nums[$p0], $nums[$curr]);
            $p0++;
            $curr++;
        } elseif ($nums[$curr] == 2) {
            list($nums[$curr], $nums[$p2]) = array($nums[$p2], $nums[$curr]);
            $p2--;
        } else {
            $curr++;
        }
    }
}

Python

def sortColors(nums):
    p0, curr, p2 = 0, 0, len(nums) - 1
    while curr <= p2:
        if nums[curr] == 0:
            nums[curr], nums[p0] = nums[p0], nums[curr]
            p0 += 1
            curr += 1
        elif nums[curr] == 2:
            nums[curr], nums[p2] = nums[p2], nums[curr]
            p2 -= 1
        else:
            curr += 1

JavaScript

function sortColors(nums) {
    let p0 = 0, curr = 0, p2 = nums.length - 1;
    while (curr <= p2) {
        if (nums[curr] === 0) {
            [nums[curr], nums[p0]] = [nums[p0], nums[curr]];
            p0++;
            curr++;
        } else if (nums[curr] === 2) {
            [nums[curr], nums[p2]] = [nums[p2], nums[curr]];
            p2--;
        } else {
            curr++;
        }
    }
}

码小课网站中有更多相关内容分享给大家学习，包括算法题解、数据结构、面试技巧等，帮助大家提升编程能力。