Fork me on GitHub

每天一道编程题(03)-荷兰国旗


经典算法

描述

现有红白蓝三个不同颜色的小球,乱序排列在一起,请重新排列这些小球,使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗问题,是因为我们可以将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。

Leetcode版本

75.分类颜色

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 012 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:
输入:[2,0,2,1,1,0]
输出:[0,0,1,1,2,2]

进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?
考查知识点:排序算法

一、解决方法(一):
用三个变量记录red,white,blue的下标位置。
1.如果nums[i] == 0 ,插入redwhite blue有影响,blue先整体向后移动一位,white再整体向后移动一位,如果不移动,前面插入的数据就会覆盖已有的。
2.如果nums[i] == 1,插入whiteblue有影响,blue整体向后移动一位。
3.如果nums[i] == 2,直接插入blue

二、解决方法(二):
快速排序思想!重要!!!

  • 我们可以把数组分成三部分,前部(全部是0),中部(全部是1)和后部(全部是2)三个部分,每一个元素(红白蓝分别对应0、1、2)必属于其中之一。

  • 将前部和后部各排在数组的前边和后边,中部自然就排好了。

  • 设置两个指针low指向前部的末尾的下一个元素(刚开始默认前部无0,所以指向第一个位置),high指向后部开头的前一个位置(刚开始默认后部无2,所以指向最后一个位置),然后设置一个遍历指针i,从头开始进行遍历。

具体步骤

  1. 若遍历到的位置为1,则说明它一定属于中部,根据总思路,中部的我们都不动,然后i向前移动一个位置。

  2. 若遍历到的位置为0,则说明它一定属于前部,于是就和low位置进行交换,然后i向前移动一个位置,low也向前移动一个位置(表示前边的已经都排好了)。

  3. 若遍历到的位置为2,则说明它一定属于后部,于是就和high位置进行交换,由于交换完毕后high指向的可能是属于前部的,若此时i前进则会导致该位置不能被交换到前部,所以此时i不前进。而同1),high向前移动一个位置。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution{
void sortColors(vector<int>& nums)
{
int temp = 0 , low = 0,high = nums.size()-1,mid = 0;
while(mid <= high)
{
if(nums[mid] == 0)
{
temp = nums[low];
nums[low] = nums[mid];
nums[mid] = temp;
low++;
mid++;
}else if(nums[mid] == 1){
mid++;
}else if(nums[mid] == 2)
{
temp = nums[high];
nums[high] = nums[mid];
nums[mid] = temp;
high--;
}
}
}
};

第三种方法:计数排序法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution{
void sortColors(vector<int>& nums)
{
int num1 = 0 ,num2 = 0, num3 = 0;
int n = nums.size();
for(int i = 0 ; i < n ; i++)
{
if(nums[i] == 0)
num1++;
else if(nums[i] == 1)
num2++;
else if(nums[i] == 2)
num3++;
}

for(int i = 0 ; i < num1 ; i++)
nums[i] = 0;
for(int i = 0 ; i < num2 ; i++)
nums[i+num1] = 1;
for(int i = 0 ; i < num3 ; i++)
nums[i+num1+num2] = 2;
}
};

执行情况

屏幕快照 2018-06-05 16.03.19.png

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%