leetcode75. 颜色分类
leetcode75. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums
目录
- leetcode75. 颜色分类
- 题目分析
- 算法介绍
- 算法步骤
- 算法流程
- 算法代码
- 算法分析
- 相似题目
题目分析
这是一个关于数组排序的算法题。题目要求实现一个函数sortColors，该函数接受一个整数数组nums，其中每个元素可以是0、1或2，并将其重新排列，使得所有0都排在数组的前面，1排在中间，2排在最后。
算法介绍
为了实现这个目标，我们可以使用三个指针：一个用于记录0的位置，一个用于记录1的位置，另一个用于记录2的位置。首先，我们遍历数组，统计每个数字的出现次数，然后根据这些统计信息重新排列数组。
算法步骤
- 初始化三个指针：
red（0的位置），white（1的位置），blue（2的位置）。 - 遍历数组
nums，统计0、1、2的出现次数。 - 将所有0放入数组的前
red个位置。 - 将所有1放入数组的
red到red+white个位置。 - 将所有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)，因为除了输入数组外，我们只使用了常数个额外空间。
- 易错点：
- 确保正确地统计每个数字的出现次数。
- 在重新排列数组时，确保每个数字都被正确地放置到对应的位置。
相似题目
| 题目 | 链接 |
|---|---|
| 颜色分类 | LeetCode 75 |
| 数组排序 | LeetCode 164 |
请注意，以上表格仅为示例，实际链接可能需要根据具体平台和题目编号进行调整。