浅谈Dutch National Flag Problem荷兰国旗问题

Dutch National Flag Problem 荷兰国旗问题,该问题由荷兰计算机科学家Dijkstra所提出

abstract.jpeg

问题描述

Dutch National Flag Problem 荷兰国旗问题描述了这样一个问题:荷兰国旗由红、白、蓝三种颜色组成。现在给定n个这三种颜色的小球,且乱序排列在一起。现期望对这些小球进行排序,使得所有相同颜色的球在一起,且颜色顺序依次为红、白、蓝。该问题对于排序算法的设计具有重要意义

事实上LeetCode的第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]

提示:
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

解决方案

计数排序

由于待排序元素只有三种:0、1、2。故我们可以使用计数排序来解决该问题。即先分别统计0、1、2出现的次数,然后重写整个数组即可

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
26
27
28
29
30
31
32
/**
* 计数排序
*/
class Solution {
public void sortColors(int[] nums) {
int num0 = 0;
int num1 = 0;
int num2 = 0;
for (int num : nums) {
if( num==0 ) {
num0++;
} else if (num == 1) {
num1++;
} else if (num == 2) {
num2++;
}
}

for (int i=0; i< nums.length; i++) {
if( num0>0 ) {
nums[i] = 0;
num0--;
} else if( num1>0 ) {
nums[i] = 1;
num1--;
} else if( num2>0 ) {
nums[i] = 2;
num2--;
}
}
}
}

单指针

我们先将所有的0交换到数组的头部,然后再将所有的1再交换到这些的0后面。这样我们就完成了排序。具体地:

  • 在第一轮遍历中,我们使用一个指针p用于表示数组该位置之前的元素全为0。显然初始状态指向的是数组0位置。当遍历过程中,每发现一个0时,即将当前元素与p指针所指向的元素进行交换。并同时将指针p向后移动一位,以指向下一个位置
  • 当第一轮遍历结束后,p指针之前的元素显然全部是0。而p指针所指向的元素及其后面元素只可能是1和2。故此时我们只需从p指针开始继续遍历。将后面的1交换到p指针位置处,同时将指针p向后移动一位,以指向下一个位置
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
26
27
28
29
30
/**
* 单指针
*/
class Solution {
public void sortColors(int[] nums) {
int p = 0;
// 先把0交换到指针p所指示的位置处
for(int i=0; i<nums.length; i++) {
if( nums[i]==0 ) {
swap(nums, i, p);
p++;
}
}

// 此时p之前的元素已经全部为0, 故只需从p开始继续遍历
// 将1交换到指针p所指示的位置处
for(int i=p; i<nums.length; i++) {
if( nums[i]==1 ) {
swap(nums, i, p);
p++;
}
}
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

双指针

同时移动0、1

通过单指针的思路,我们不难想到。我们是不是可以用两个指针同时移动0、1。这样只需一轮遍历即可。即用p0指针来交换0、用p1指针来交换1。这样p0指针之前的位置都是0,而p0指针到p1指针之前的位置都是1。显然这两个指针初始状态均为0。具体地

  • 当我们遍历过程中遇到1时,显然非常简单。直接将当前元素与p1位置元素进行交换即可。同时将p1指针向后移动一位,以指向下一个位置
  • 当我们遍历过程中遇到0时,如果p0、p1指针均指向相同位置时,我们只需将当前元素与p0位置元素进行交换即可。同时将p0、p1指针均向后移动一位,以指向下一个位置;但当如果p0在p1指针前面时,此时说明p0指针所指向的元素一定是1。故当我们将当前元素与p0位置元素进行交换后,会导致原p0指针指向的1被放置到了当前遍历的位置上。所以此时还需要再进行一次交换,即将当前遍历位置上最新元素再次与p1指针进行交换。随后同时将p0、p1指针均向后移动一位,以指向下一个位置。示意图如下所示

figure 1.jpeg

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
26
27
28
29
30
31
32
/**
* 双指针: 同时移动0、1
*/
class Solution {
public void sortColors(int[] nums) {
int p0 = 0;
int p1 = 0;
for(int i=0; i<nums.length; i++) {
// 如果当前元素为1, 直接将其交换到p1指针处
if( nums[i]==1) {
swap(nums, i, p1);
p1++;
} else if( nums[i]==0 ) {
// 如果当前元素为0, 直接将其交换到p0指针处
swap(nums, i, p0); // (1) 处
// 如果p0、p1指针指向不是同一个位置, 则说明p0位置原先指向的是1
if( p0<p1 ) {
// 由于(1)处把1交换到i位置, 故需要再次将i位置的元素放置到p1指针处
swap(nums, i, p1);
}
p0++;
p1++;
}
}
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

同时移动0、2

事实上,我们还可以使用两个指针:p0、p2,以实现同时将0、2移动到数组的头部、尾部。即用p0指针来交换0、用p2指针来交换2。这样p0指针之前的位置都是0,而p2之后的位置都是2。显然这两个指针初始状态分别为0、nums.length-1。由于遍历过程是从左到右的,而p2指针是从右到左的。故遍历位置时一旦超过p2指针就可以终止了,具体地

  • 当我们遍历过程中遇到0时,显然非常简单。直接将当前元素与p0位置元素进行交换即可。同时将p0指针向后移动一位,以指向下一个位置
  • 当我们遍历过程中遇到2时,同样需要将当前元素与p2位置元素进行交换。同时将p2指针向前移动一位,以指向前一个位置。但问题来了,由于p2指针原先指向的元素未被遍历过。所以它可能是0、1、2中的任意一个。所以当该元素被交换当前遍历位置后,我们还需要继续处理该元素,而不能直接去遍历下一个位置的元素
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
26
27
28
29
/**
* 双指针: 同时移动0、2
*/
class Solution {
public void sortColors(int[] nums) {
int p0 = 0;
int p2= nums.length-1;

for(int i=0; i<nums.length; i++) {
// 如果当前元素为2, 直接将其交换到p2指针处
while (i<=p2 && nums[i]==2) {
swap(nums, i, p2);
p2--;
}

// 如果当前元素为0, 直接将其交换到p0指针处
if( nums[i]==0 ) {
swap(nums, i, p0);
p0++;
}
}
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
0%