如果你想在校招中顺利拿到更好的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
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
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
2
3
4
5
6
7
8
9
10
11