75. 颜色分类¶
难度：中等
题目¶
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]
提示：
n == nums.length1 <= n <= 300nums[i]为0、1或2
进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
题解¶
- 统计数组中
0、1和2的出现次数，按照出现次数重新生成数组。 - 使用快速排序的思路，若出现
0则移动到数组开头，若出现2则移动到数组结尾。
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void sortColors(int* nums, int numsSize){
int head = 0, tail = numsSize - 1, i = 0;
for (i = 0; i <= tail && tail > head; i++)
{
if (nums[i] == 0)
swap(nums + head++, nums + i);
if (nums[i] == 2)
swap(nums + tail--, nums + i--);
}
}