题目描述给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。示例 1输入nums [2,0,2,1,1,0]输出[0,0,1,1,2,2]解释该数组包含两个 0、两个 1 和两个 2。将它们原地排序后所有 0 排在最前面接着是所有 1最后是所有 2。示例 2输入nums [2,0,1]输出[0,1,2]解释数组中有且仅有一个 0、一个 1 和一个 2按 0、1、2 的顺序原地排列。解题思路方法一三指针荷兰国旗问题核心思路用三个指针把数组分成三个区域[0, left)全是 0[left, i)全是 1(right, n-1]全是 2[i, right]待处理区域三个指针指针含义left0 区域的右边界下一个 0 应该放的位置i当前遍历位置right2 区域的左边界下一个 2 应该放的位置规则nums[i] 0交换nums[left]和nums[i]leftinums[i] 1inums[i] 2交换nums[i]和nums[right]right--不移动 i关键遇到 2 时交换后i不移动因为换过来的数还没检查。具体过程示例nums [2, 0, 2, 1, 1, 0]初始: left0, i0, right5 [2, 0, 2, 1, 1, 0] ↑ ↑ left,i right i0, nums[0]2: 交换 nums[0] 和 nums[5] [0, 0, 2, 1, 1, 2] ↑ ↑ left,i right right4, i 不动 i0, nums[0]0: 交换 nums[0] 和 nums[0]自己left1, i1 [0, 0, 2, 1, 1, 2] ↑ ↑ left,i right i1, nums[1]0: 交换 nums[1] 和 nums[1]left2, i2 [0, 0, 2, 1, 1, 2] ↑ ↑ left,i right i2, nums[2]2: 交换 nums[2] 和 nums[4] [0, 0, 1, 1, 2, 2] ↑ ↑ left,i right right3, i 不动 i2, nums[2]1: i3 [0, 0, 1, 1, 2, 2] ↑ ↑ left i,right i3, nums[3]1: i4 i4 right3结束 结果: [0, 0, 1, 1, 2, 2] ✅代码实现class Solution { public: void sortColors(vectorint nums) { int left 0; int i 0; int right nums.size() - 1; while (i right) { if (nums[i] 0) { swap(nums[left], nums[i]); left; i; } else if (nums[i] 1) { i; } else { // nums[i] 2 swap(nums[i], nums[right]); right--; // 注意i 不移动 } } } };复杂度分析维度复杂度说明时间复杂度O(n)每个元素最多被访问一次空间复杂度O(1)原地修改只用三个指针关键细节1. 为什么遇到 2 时i不移动因为交换后nums[i]变成了原来nums[right]的值这个值还没被检查需要下一轮继续判断。2. 为什么遇到 0 时i要移动因为left指向的位置要么是 0要么是 1不可能是 2因为 2 都被换到右边了。交换后nums[i]是 1已经处理过了可以i。3. 循环条件为什么是i right因为[i, right]是待处理区域当i right时所有元素都处理完了。方法二计数排序两次遍历代码实现class Solution { public: void sortColors(vectorint nums) { int count[3] {0}; // 第1次遍历统计每个值的出现次数 for (int x : nums) { count[x]; } // 第2次遍历按顺序填充 int idx 0; for (int i 0; i 3; i) { for (int j 0; j count[i]; j) { nums[idx] i; } } } };复杂度时间 O(n)空间 O(1)缺点需要遍历两次数组。方法三单指针两次遍历代码实现class Solution { public: void sortColors(vectorint nums) { int n nums.size(); int ptr 0; // 第1次把所有 0 移到前面 for (int i 0; i n; i) { if (nums[i] 0) { swap(nums[i], nums[ptr]); ptr; } } // 第2次把所有 1 移到 0 后面 for (int i ptr; i n; i) { if (nums[i] 1) { swap(nums[i], nums[ptr]); ptr; } } } };复杂度时间 O(n)空间 O(1)缺点需要遍历两次数组。三种方法对比方法时间复杂度空间复杂度遍历次数推荐度三指针荷兰国旗O(n)O(1)1次⭐⭐⭐⭐⭐计数排序O(n)O(1)2次⭐⭐⭐⭐单指针O(n)O(1)2次⭐⭐⭐⭐总结要点说明核心思想三指针分区0 区、1 区、2 区关键操作遇到 0 交换左指针遇到 2 交换右指针时间复杂度O(n)空间复杂度O(1) 【双指针-6】75.颜色分类
题目描述给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。示例 1输入nums [2,0,2,1,1,0]输出[0,0,1,1,2,2]解释该数组包含两个 0、两个 1 和两个 2。将它们原地排序后所有 0 排在最前面接着是所有 1最后是所有 2。示例 2输入nums [2,0,1]输出[0,1,2]解释数组中有且仅有一个 0、一个 1 和一个 2按 0、1、2 的顺序原地排列。解题思路方法一三指针荷兰国旗问题核心思路用三个指针把数组分成三个区域[0, left)全是 0[left, i)全是 1(right, n-1]全是 2[i, right]待处理区域三个指针指针含义left0 区域的右边界下一个 0 应该放的位置i当前遍历位置right2 区域的左边界下一个 2 应该放的位置规则nums[i] 0交换nums[left]和nums[i]leftinums[i] 1inums[i] 2交换nums[i]和nums[right]right--不移动 i关键遇到 2 时交换后i不移动因为换过来的数还没检查。具体过程示例nums [2, 0, 2, 1, 1, 0]初始: left0, i0, right5 [2, 0, 2, 1, 1, 0] ↑ ↑ left,i right i0, nums[0]2: 交换 nums[0] 和 nums[5] [0, 0, 2, 1, 1, 2] ↑ ↑ left,i right right4, i 不动 i0, nums[0]0: 交换 nums[0] 和 nums[0]自己left1, i1 [0, 0, 2, 1, 1, 2] ↑ ↑ left,i right i1, nums[1]0: 交换 nums[1] 和 nums[1]left2, i2 [0, 0, 2, 1, 1, 2] ↑ ↑ left,i right i2, nums[2]2: 交换 nums[2] 和 nums[4] [0, 0, 1, 1, 2, 2] ↑ ↑ left,i right right3, i 不动 i2, nums[2]1: i3 [0, 0, 1, 1, 2, 2] ↑ ↑ left i,right i3, nums[3]1: i4 i4 right3结束 结果: [0, 0, 1, 1, 2, 2] ✅代码实现class Solution { public: void sortColors(vectorint nums) { int left 0; int i 0; int right nums.size() - 1; while (i right) { if (nums[i] 0) { swap(nums[left], nums[i]); left; i; } else if (nums[i] 1) { i; } else { // nums[i] 2 swap(nums[i], nums[right]); right--; // 注意i 不移动 } } } };复杂度分析维度复杂度说明时间复杂度O(n)每个元素最多被访问一次空间复杂度O(1)原地修改只用三个指针关键细节1. 为什么遇到 2 时i不移动因为交换后nums[i]变成了原来nums[right]的值这个值还没被检查需要下一轮继续判断。2. 为什么遇到 0 时i要移动因为left指向的位置要么是 0要么是 1不可能是 2因为 2 都被换到右边了。交换后nums[i]是 1已经处理过了可以i。3. 循环条件为什么是i right因为[i, right]是待处理区域当i right时所有元素都处理完了。方法二计数排序两次遍历代码实现class Solution { public: void sortColors(vectorint nums) { int count[3] {0}; // 第1次遍历统计每个值的出现次数 for (int x : nums) { count[x]; } // 第2次遍历按顺序填充 int idx 0; for (int i 0; i 3; i) { for (int j 0; j count[i]; j) { nums[idx] i; } } } };复杂度时间 O(n)空间 O(1)缺点需要遍历两次数组。方法三单指针两次遍历代码实现class Solution { public: void sortColors(vectorint nums) { int n nums.size(); int ptr 0; // 第1次把所有 0 移到前面 for (int i 0; i n; i) { if (nums[i] 0) { swap(nums[i], nums[ptr]); ptr; } } // 第2次把所有 1 移到 0 后面 for (int i ptr; i n; i) { if (nums[i] 1) { swap(nums[i], nums[ptr]); ptr; } } } };复杂度时间 O(n)空间 O(1)缺点需要遍历两次数组。三种方法对比方法时间复杂度空间复杂度遍历次数推荐度三指针荷兰国旗O(n)O(1)1次⭐⭐⭐⭐⭐计数排序O(n)O(1)2次⭐⭐⭐⭐单指针O(n)O(1)2次⭐⭐⭐⭐总结要点说明核心思想三指针分区0 区、1 区、2 区关键操作遇到 0 交换左指针遇到 2 交换右指针时间复杂度O(n)空间复杂度O(1)