个人技术分享

大家好！我是曾续缘💘

今天是《LeetCode 热题 100》系列

发车第 98 天

技巧第 3 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

颜色分类

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

进阶：

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

难度：💖💖

解题方法

这道题目是要求对一个数组进行排序，数组中包含红色(0)、白色(1)和蓝色(2)三种元素，要求将相同颜色的元素相邻，并按照红色、白色、蓝色的顺序排列。

1. 首先定义两个指针 p0 和 p1，初始值都为 0。这两个指针分别用来标记下一个应该放置 0 的位置和下一个应该放置 1 的位置。
2. 遍历数组，如果当前元素为 1，则将其与指针 p1 指向的元素交换，并将 p1 向后移动一位。
3. 如果当前元素为 0，则将其与指针 p0 指向的元素交换。此时需要判断 p0 是否小于 p1，若是，则再将**新的当前元素1**与 p1 指向的元素交换，然后分别将 p0 和 p1 向后移动一位。
4. 遍历完成后，数组就会按照要求进行排序。

Code

class Solution {
    // 定义一个方法来排序数组
    public void sortColors(int[] nums) {
        int n = nums.length; // 获取数组的长度
        int p0 = 0, p1 = 0; // 初始化两个指针，p0和p1
        // 遍历数组中的每一个元素
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                // 如果当前元素是1，那么它应该位于p0和p1之间
                swap(nums, i, p1);
                ++p1; // 将p1向前移动一位
            } else if (nums[i] == 0) {
                // 如果当前元素是0，那么它应该位于最前面
                swap(nums, i, p0);
                if (p0 < p1) {
                    // 如果p0小于p1，那么说明0被交换到了p1的位置，
                    // 此时需要将p1位置的元素交换回p0位置
                    swap(nums, i, p1);
                }
                ++p0; // 将p0向前移动一位
                ++p1; // 同时将p1也向前移动一位
            }
        }
    }

    // 定义一个方法来交换数组中的两个元素
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}