75.颜色分类

LeetCode LeetCode 热题100 数组排序双指针

发布时间 : 2000-01-10 00:07

字数:1.5k 阅读 :

评论:

75.颜色分类

75.颜色分类

75.1 题目

给定一个包含红色、白色和蓝色的元素的数组 nums，共有 n 个元素，使用整数 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

进阶：

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

75.2 题解

方法一：计数排序

思路

第一趟扫描统计 0、1、2 各自出现的次数。第二趟扫描根据统计结果重写数组：先填 0，再填 1，最后填 2。两趟扫描，逻辑简单清晰。

核心思想：统计各元素数量，按顺序重写数组。

具体步骤：

第一趟：统计 0、1、2 的数量。
第二趟：按顺序重写数组，先填 0，再填 1，最后填 2。

举例：对于 nums = [2,0,2,1,1,0]：

统计：count0=2, count1=2, count2=2
重写：[0,0,1,1,2,2]

复杂度分析

时间复杂度：O(n)，两趟扫描。
空间复杂度：O(1)，只使用常数额外空间存储计数。

代码

// 方法一：使用计数排序的思想，两趟扫描
static void SortColors1(int[] nums)
{
    // 统计每种颜色的个数
    int count0 = 0, count1 = 0, count2 = 0;
    foreach (var num in nums)
    {
        if (num == 0)
            count0++;
        else if (num == 1)
            count1++;
        else if (num == 2)
            count2++;
    }

    // 根据统计值重写数组
    int i = 0;
    while (count0 > 0)
    {
        nums[i++] = 0;
        count0--;
    }

    while (count1 > 0)
    {
        nums[i++] = 1;
        count1--;
    }

    while (count2 > 0)
    {
        nums[i++] = 2;
        count2--;
    }
}

方法二：三指针一趟扫描（荷兰国旗问题）

思路

使用三个指针：left 指向已排好的 0 的右边界，right 指向已排好的 2 的左边界，curr 为当前遍历位置。

遍历数组：

如果当前元素是 0，交换到 left 位置，left++，curr++
如果当前元素是 2，交换到 right 位置，right--（不移动 curr，因为交换过来的元素还需要检查）
如果当前元素是 1，直接 curr++

一趟扫描完成排序。

举个例子：nums = [2,0,2,1,1,0]

left=0, right=5, curr=0
curr=0, nums[0]=2，交换到right：[0,0,2,1,1,2]，right=4
curr=0, nums[0]=0，交换到left：[0,0,2,1,1,2]，left=1, curr=1
继续直到完成

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

代码

// 方法二：使用指针多趟扫描
static void SortColors2(int[] nums)
{
    int left = 0; // 左指针，指向已经排好的0的右边界
    int right = nums.Length - 1; // 右指针，指向已经排好的2的左边界

    int curr = 0; // 当前考虑的元素

    while (curr <= right)
    {
        if (nums[curr] == 0)
        {
            // 如果当前元素为0，交换到左边界
            Swap(nums, curr, left);
            left++;
            curr++;
        }
        else if (nums[curr] == 2)
        {
            // 如果当前元素为2，交换到右边界
            Swap(nums, curr, right);
            right--;
        }
        else
        {
            // 如果当前元素为1，直接跳过
            curr++;
        }
    }
}

// 辅助函数：交换数组中的两个元素
static void Swap(int[] nums, int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

75.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，
        // 原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
        // 使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

        // 示例 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

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

        #endregion

        #region 测试

        // 示例 1 方法1
        int[] nums1 = { 2, 0, 2, 1, 1, 0 };
        SortColors1(nums1);
        Console.WriteLine($"示例1 方法1 输出：[{string.Join(",", nums1)}]");

        // 示例 1 方法2
        int[] nums2 = { 2, 0, 2, 1, 1, 0 };
        SortColors2(nums2);
        Console.WriteLine($"示例1 方法2 输出：[{string.Join(",", nums2)}]");

        // 示例 2 方法1
        int[] nums3 = { 2, 0, 1 };
        SortColors1(nums3);
        Console.WriteLine($"示例2 方法1 输出：[{string.Join(",", nums3)}]");

        // 示例 2 方法2
        int[] nums4 = { 2, 0, 1 };
        SortColors2(nums4);
        Console.WriteLine($"示例2 方法2 输出：[{string.Join(",", nums4)}]");

        #endregion
    }

    #region 答案

    // 方法一：使用计数排序的思想，两趟扫描
    static void SortColors1(int[] nums)
    {
        // 统计每种颜色的个数
        int count0 = 0, count1 = 0, count2 = 0;
        foreach (var num in nums)
        {
            if (num == 0)
                count0++;
            else if (num == 1)
                count1++;
            else if (num == 2)
                count2++;
        }

        // 根据统计值重写数组
        int i = 0;
        while (count0 > 0)
        {
            nums[i++] = 0;
            count0--;
        }

        while (count1 > 0)
        {
            nums[i++] = 1;
            count1--;
        }

        while (count2 > 0)
        {
            nums[i++] = 2;
            count2--;
        }
    }

    // 方法二：使用指针多趟扫描
    static void SortColors2(int[] nums)
    {
        int left = 0; // 左指针，指向已经排好的0的右边界
        int right = nums.Length - 1; // 右指针，指向已经排好的2的左边界

        int curr = 0; // 当前考虑的元素

        while (curr <= right)
        {
            if (nums[curr] == 0)
            {
                // 如果当前元素为0，交换到左边界
                Swap(nums, curr, left);
                left++;
                curr++;
            }
            else if (nums[curr] == 2)
            {
                // 如果当前元素为2，交换到右边界
                Swap(nums, curr, right);
                right--;
            }
            else
            {
                // 如果当前元素为1，直接跳过
                curr++;
            }
        }
    }

    // 辅助函数：交换数组中的两个元素
    static void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    #endregion
}

75.4 运行结果

示例1 方法1 输出：[0,0,1,1,2,2]
示例1 方法2 输出：[0,0,1,1,2,2]
示例2 方法1 输出：[0,1,2]
示例2 方法2 输出：[0,1,2]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com