Keshawn_lu's Blog

Leetcode 75. 颜色分类

字数统计: 431阅读时长: 1 min
2020/10/07 Share

题目简介:

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

1
2
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶:

  • 一个直观的解决方案是使用计数排序的两趟扫描算法。
  • 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
  • 你能想出一个仅使用常数空间的一趟扫描算法吗?

思路:

这题实际上就是排个序,由于只有三种颜色,我们可以先忽略1的情况,将0都放到最前面。将2都放到最后面,这样一样0和2的位置确定了,1的位置也相应确定下来了。

所以使用双指针的方法进行交换数字。

tip:

  • 将2换到后面时,由于不能确定从后面换过来的数字是否依然为2,所以i不能++,否则这个2会卡在这里,无法被处理。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:

void sortColors(vector<int>& nums) {

int left = 0;
int right = nums.size() - 1;

int i = 0;
while(i <= right){ //i超过right时,已排序完成

if(nums[i] == 0){

nums[i] = nums[left];
nums[left] = 0; //交换

left++;
i++;
}
else if(nums[i] == 2){

nums[i] = nums[right];
nums[right] = 2;

right--;
// i++; 这里i不能++,会出错
}
else
i++; //跳过1的情况
}
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: