文章目录
- 1.题目
- [75. 颜色分类](https://leetcode.cn/problems/sort-colors/description/?envType=problem-list-v2&envId=qVg9d5vs)
- 2.思路
- 3.代码
1.题目
75. 颜色分类
给定一个包含红色、白色和蓝色、共 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`
2.思路
- 定义两个指针：
left：指向数组的最左边，表示 0（红色）的边界。right：指向数组的最右边，表示 2（蓝色）的边界。
- 遍历数组：
- 如果当前数字是 0，就把它放到
left的位置，然后left向右移动。 - 如果当前数字是 2，就把它放到
right的位置，然后right向左移动。 - 如果当前数字是 1，就跳过，继续遍历。
- 如果当前数字是 0，就把它放到
注意：left 初始化为-1是因为最开始没有安排好第一个位置，所以不好初始化为0，right同理
3.代码
class Solution {
public:void sortColors(vector<int>& nums) {// 定义两个指针，left 指向 0 的边界，right 指向 2 的边界int left = -1, right = nums.size();// tmp 是当前遍历的位置int tmp = 0;// 遍历数组while (tmp < right) {if (nums[tmp] == 0) {// 如果当前数字是 0，把它放到 left 的位置++left; // left 向右移动swap(nums[tmp], nums[left]); // 交换当前数字和 left 位置的数字++tmp; // 继续遍历下一个数字} else if (nums[tmp] == 2) {// 如果当前数字是 2，把它放到 right 的位置--right; // right 向左移动swap(nums[tmp], nums[right]); // 交换当前数字和 right 位置的数字// 注意：这里不需要移动 tmp，因为交换后的数字可能是 0 或 1，需要再次检查} else {// 如果当前数字是 1，直接跳过++tmp; // 继续遍历下一个数字}}}
};