一首歌的时间看懂荷兰三色旗问题
程序员文章站
2022-03-04 17:55:24
...
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
下面看下代码:
/*
荷兰三色旗问题解
*/
class Solution {
public:
//p0追踪0的最右边界,p2追踪2的最左边界
void sortColors(vector<int>& nums) {
// 对于所有 idx < p0 : nums[idx < p0] = 0
// curr 是当前考虑元素的下标
int p0 = 0, curr = 0;
// 对于所有 idx > p2 : nums[idx > p2] = 2
//p2首先指向数组最后一个下标
int p2 = nums.size() - 1;
while (curr <= p2) {
if (nums[curr] == 0) {
swap(nums[curr++], nums[p0++]);
} else if (nums[curr] == 2) {
swap(nums[curr], nums[p2--]);
}
else curr++;
}
}
};
该算法用了用3个指针,p0追踪0的最右边界,p2追踪2的最左边界 ,curr表示当前下标。遇到等于0或2的时候就进行交换,并且对p0或p2进行操作,思路很巧妙。
时间复杂度:O(N)
空间复杂度:O(1)
参考地址:https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode/
推荐阅读