75.颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：输入：nums = [2,0,1] 输出：[0,1,2]
分析:
1.该问题为经典的 [荷兰国旗问题], 不使用排序去做
2.最基础的想法是计数排序, 扫一遍统计出 0/1/2 的个数, 然后再扫一遍按照元素数量去覆盖数组
class Solution {
public:
void sortColors(vector<int>& nums) {
int len0 = 0;
int len1 = 0;
int len2 = 0;
for (auto& x : nums) {
if (x == 0) {
++len0;
}
if (x == 1) {
++len1;
}
if (x == 2) {
++len2;
}
}
int i = 0;
while (i < nums.size()) {
if (i < len0) {
nums[i] = 0;
} else if (i < len0 + len1) {
nums[i] = 1;
} else {
nums[i] = 2;
}
++i;
}
}
}
3.利用三向切分 partition 的思想去进行交换, 在三向切分 Partition里面是维护两个指针分别指向 < target 的位置和 > target 的位置, 在荷兰国旗问题里面类似是指向 < 1 和 > 1 的位置
class Solution {
public:
void sortColors(vector<int>& nums) {
int len = nums.size();
int p0 = 0; // 指向0的做开区间, 最终指向1的左端点
int p2 = len-1; // 指向2的左开区间, 最终指向1的右端点
int i = 0;
while (i <= p2) {
if (nums[i] == 0) {
swap(nums[i++], nums[p0++]);
} else if (nums[i] == 2) {
swap(nums[i], nums[p2--]);
} else if (nums[i] == 1) {
++i;
}
}
return;
}
};
更优雅的版本: 只一次扫描能解决, 就用覆盖来代替交换
维护 p0 写入和 p1 写入点两个指针, 扫描数组, 对于 nums[i] 来说, 不管是几先暂定是2, 这个 2 后续会因为 p0 和 p1 可能发生的写入而覆盖掉, 然后根据值 num 再决定 p0 和 p1 的相应写入和移动过程
(i) num == 0 或者 num == 1 的情况下, p1 指针写入并移动
(ii). num == 0 的情况下 p0 指针写入并移动
class Solution {
public:
void sortColors(vector<int>& nums) {
int p0 = 0; // p0 指向 0 的写入点
int p1 = 0; // p1 指向 1 的写入点
for (int i = 0; i < nums.size(); ++i) {
int num = nums[i];
// 不管是几先暂定写入2
nums[i] = 2;
// 如果 num < 2的情况下, p1指针写入并移动
if (num < 2) {
nums[p1++] = 1;
}
// 如果 num == 0 的情况下, p0指针写入并移动
if (num == 0) {
nums[p0++] = 0;
}
}
return;
}
};
转载请注明来源, from goldandrabbit.github.io
