leetcode75. 颜色分类

leetcode75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：
输入：nums

题目分析

这是一个关于数组排序的算法题。题目要求实现一个函数sortColors，该函数接受一个整数数组nums，其中每个元素可以是0、1或2，并将其重新排列，使得所有0都排在数组的前面，1排在中间，2排在最后。

算法介绍

为了实现这个目标，我们可以使用三个指针：一个用于记录0的位置，一个用于记录1的位置，另一个用于记录2的位置。首先，我们遍历数组，统计每个数字的出现次数，然后根据这些统计信息重新排列数组。

算法步骤

1. 初始化三个指针：red（0的位置），white（1的位置），blue（2的位置）。
2. 遍历数组nums，统计0、1、2的出现次数。
3. 将所有0放入数组的前red个位置。
4. 将所有1放入数组的red到red+white个位置。
5. 将所有2放入数组的red+white到末尾的位置。

算法流程

算法代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
    int n=nums.size();
    int red=0;
    int blue=0;
    if(nums.size()==1) return ;
    for(int i=0;i<n;i++)
    {
        if(nums[i]==0) red++;
        else if(nums[i]==2) blue++;
    }
    int white=n-red-blue;
    if(red) for(int i=0;i<red;i++)
    {
        nums[i]=0;
    }
    if(white) for(int i=red;i<n-blue;i++)
    {
        nums[i]=1;
    }
    if(blue) for(int i=n-blue;i<n;i++)
    {
        nums[i]=2;
    }
    return ;
    }
};

算法分析

• 时间复杂度：O(n)，其中n是数组nums的长度。我们只需要遍历数组一次来统计数字的出现次数，然后再遍历数组一次来重新排列。
• 空间复杂度：O(1)，因为除了输入数组外，我们只使用了常数个额外空间。
• 易错点：
  • 确保正确地统计每个数字的出现次数。
  • 在重新排列数组时，确保每个数字都被正确地放置到对应的位置。

相似题目

请注意，以上表格仅为示例，实际链接可能需要根据具体平台和题目编号进行调整。