荷兰国旗问题
荷兰国旗问题,或者说黑猫白猫灰猫问题,其实都是一样的,就是说有三类数据乱序排列,然后要求用O(N)的时间复杂度,O(1)的空间复杂度使其有序。因其类似于荷兰国旗,所以被称为荷兰国旗问题(德国、法国在这里表示不服~)。
输入
0,1,2,1,2,0,1,1,0,2,1,0,1,2,2,1,0,0
输出
0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2
代码解析
排序方法:设置start/end/current三个指针,分别指向开头、开头、结尾。在current<=end的背景下,然后开始判断current的值:
1. 若current==0,因为0要排在前面,所以则将start指向的值和current的值交换,然后start++,current++;
2.若current==1,因为1是排在中间,所以current++,start不变;
3.若current==2,则将current和end的元素交换,将end--,但是current不变,如果current后移1位,那么current这一位就无法判断了。
代码实现
void sorthl(vector<int> &nums)
{
int len = nums.size();
int start = 0, current = 0, end = len - 1;
//在current<=end的背景下,然后开始判断current的值
while (current <= end)
{
//1.若current==0,则将start指向的值和current的值交换,然后start++,current++;
if (nums[current] == 0)
{
swap(nums[current], nums[start]);
++current;
++start;
}
//3.若current==2,则将current和end的元素交换,将end--,但是current不变。
else if (nums[current] == 2)
{
swap(nums[current], nums[end]);
--end;
}
//2.若current==1,则current++,start不变;
else if (nums[current] == 1)
{
++current;
}
}
}
文章评论