荷兰国旗问题也是一个比较经典的问题,荷兰旗是由三色组成,每一种颜色都有自己单独的区域,三种颜色泾渭分明。抽象一点来说,也就是分成三区间的问题。下面是一道这个问题的经典题
75. 颜色分类
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶:
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
经典的解法是将遇到的0都放到链表的左边,遇到的2都放到链表的右边,然后1自然就都位于中间。
class Solution {
public:
void sortColors(vector<int>& nums) {
int end = nums.size() - 1;
if(end <= 0)
return;
int begin = 0;
int tmp;
for(int i = 0; i <= end;)
{
if(nums[i] == 0)
{
tmp = nums[begin];
nums[begin] = nums[i];
nums[i] = tmp;
begin++;
i++;
}
else if(nums[i] == 2)
{
tmp = nums[end];
nums[end] = nums[i];
nums[i] = tmp;
end--;
}
else if(nums[i] == 1)
{
i++;
}
}
}
};
时间复杂度:由于对长度 N的数组进行了一次遍历,时间复杂度为O(N)。
空间复杂度 :由于只使用了常数空间,空间复杂度为O(1)。
class Solution {
public:
void sortColors(vector<int>& nums) {
int begin = 0, end = nums.size() - 1;
for(int i = 0; i < nums.size();)
{
if(nums[i] == 0)
{
nums[i] = nums[begin];
nums[begin] = 0;
begin++;
i = begin;
}
else if(nums[i] == 2)
{
nums[i] = nums[end];
nums[end] = 2;
end--;
}
else
{
i++;
}
if(i > end)
break;
}
}
};
还有一种解法是采用Hashmap的方法,不过相当于遍历了两次链表,同时还使用了额外的空间,唯一的好处是简单明了。
class Solution {
public:
void sortColors(vector<int>& nums) {
map<int, int>count;
for(auto &index : nums)
count[index]++;
int i = 0;
for(auto &index : count)
{
while(index.second > 0)
{
nums[i] = index.first;
index.second--;
i++;
}
}
return;
}
};