Joyce' Blog
0%

sort-colors

发表于

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

题解

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。（说实话我一开始没想到这方法……）

仅使用常数空间的一趟扫描算法：

用三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void sortColors(vector<int>& nums) {
	int vsize = nums.size();
	int p = 0, q = vsize - 1;
	while (p < vsize&&nums[p] == 0)p++;
	while (q >= 0 && nums[q] == 2)q--;
	int cur = p;
	while (cur <= q)
	{
		if (nums[cur] == 0)
		{
			swap(nums[cur], nums[p]);
			p++;
			cur++;
		}
		else if (nums[cur] == 2)
		{
			swap(nums[cur], nums[q]);
			q--;
		}
		else
			cur++;
	}
}


重点在于找边界！！

2.26：

  • 并行：代码性能测试、报告
  • ICS：报告