leetcode 75. 颜色分类
题目详情
题目链接 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。你能想出一个仅使用常数空间的一趟扫描算法吗？
我的代码
class Solution {
public:
void sortColors(vector
<int>& nums
) {
int r
= 0, w
= 0, b
= 0;
for (auto & num
: nums
) {
if (num
== 0) {
r
++;
} else if (num
== 1) {
w
++;
} else {
b
++;
}
}
for (auto & num
: nums
) {
if (r
-- > 0) {
num
= 0;
} else if (w
-- > 0) {
num
= 1;
} else {
num
= 2;
}
}
}
};
我的成绩
执行结果：通过 执行用时：4 ms, 在所有 C++ 提交中击败了57.70%的用户 内存消耗：8 MB, 在所有 C++ 提交中击败了95.10%的用户
一些想法
本道题应该是用双指针法，但我没想到怎么做，，
执行用时为 0 ms 的范例
class Solution {
public:
void sortColors(vector
<int>& nums
) {
int right_0
= 0, left_2
= nums
.size()-1;
int i
=0;
int temp
=0;
while(i
<=left_2
)
{
if(nums
[i
]==0)
{
temp
=nums
[i
];
nums
[i
]=nums
[right_0
];
nums
[right_0
]=temp
;
right_0
++;
++i
;
}
else if(nums
[i
]==2)
{
temp
=nums
[i
];
nums
[i
]=nums
[left_2
];
nums
[left_2
]=temp
;
left_2
--;
}
else
++i
;
}
}
};
思考
参见官方解答
