如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习校招总结offer选择也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 75. 颜色分类

力扣原题链接(点我直达) (opens new window)

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

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

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

示例:

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

进阶:

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

# 第一版,直接解出来

执行用时 :4 ms, 在所有 cpp 提交中击败了90.02%的用户

内存消耗 :8.5 MB, 在所有 cpp 提交中击败了51.89%的用户

void sortColors(vector<int>& nums) {
	int zeroCut=0, oneCut=0, twoCut=0;

	for (auto& n : nums) {
		if (n == 0) zeroCut++;
		else if (n == 1) oneCut++;
		else twoCut++;
	}

	for (size_t i = 0; i < nums.size(); ++i) {
		if (i < zeroCut) nums[i] = 0;
		else if (i >= zeroCut && i < zeroCut + oneCut) nums[i] = 1;
		else
			nums[i] = 2;

	}


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 第二版,进阶,双路快排的思想,感觉时间不太对

执行用时 :0 ms, 在所有 cpp 提交中击败了100.00%的用户

内存消耗 :8.5 MB, 在所有 cpp 提交中击败了50.30%的用户

    void sortColors(vector<int>& nums) {
	int low = 0, high = nums.size() - 1,index=-1;
	while (low<=high)
	{
		if (nums[low] == 0) swap(nums[++index], nums[low++]);
		else if (nums[low] == 2) swap(nums[high--], nums[low]);
		else
			low++;
	}	
        
    }
1
2
3
4
5
6
7
8
9
10
11