给定一个包含红色、白色和蓝色，一共 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]
进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
双指针，把 0 移到前面，2 移到后面，1 自然就在中间。采用 swap 交换，但会存在不同位置的 2 和 2 交换，需要指针回退再交换一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
void sortColors(vector<int>& nums) {
int pt0=0,pt2=nums.size()-1;
int i=0;
while(i<=pt2){
if(nums[i]==0)
swap(nums[i++],nums[pt0++]);
else if(nums[i]==2)
swap(nums[i],nums[pt2--]);
else i++;
}
}
};
|
大佬的妙啊，我这破脑袋想不出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public void sortColors(int[] nums) {
int num0 = 0, num1 = 0, num2 = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == 0) {
nums[num2++] = 2;
nums[num1++] = 1;
nums[num0++] = 0;
}else if(nums[i] == 1) {
nums[num2++] = 2;
nums[num1++] = 1;
}else {
nums[num2++] = 2;
}
}
}
}
|
