高频面试考题荷兰旗问题

38次阅读

共计 1096 个字符,预计需要花费 3 分钟才能阅读完成。

荷兰旗问题又称三色排序,或者彩虹排序,

因为荷兰旗就三种颜色嘛,那这道题的问题就是给你三种颜色,按照给定的顺序排好。

当然了,题目的问法各种各样,有的给数字,有的给字母,但本质都是一样的。

比如给你一个只含有三个数字的数组:312312312231111122113,
要求按照 1 2 3 的顺序排好,即:
111111111222222222223333333333
(请不要真的去数数,认真你就输了)

还是用我们经典的「挡板法」。

在快排中,我们用了两个挡板把数组分成三个区域:

<= pivot;未排序区间;> pivot

那么这里就要三个挡板,分成四个区域:

1, 2, 3, 未排序区间

Partition

具体说来,用 i, j, k 这三个指针分一下:
[0, i): 存 1
[i, j): 存 2

(k, array.length-1]: 存 3

这里 j 放在未排序区间的左边和右边都行,但基本上大家都是放左边,所以我们也没必要“标新立异”。

初始化:

i = 0;
j = 0;
k = array.length – 1;
这样才能保证 1,2,3 的每个区间都为空。

我们通过 观察指针 j 指向的元素 来不断缩小未排序区间,直到为空。

例子:1232312

为了好看,排好序的元素我们用 RGB 三原色标示一下。

Step1.

指针 j 指向 1,而 1 应该放在 [0, i) 区间内,
这里应该把指针 i 和指针 j 所指的元素交换一下,并且俩指针往前走。

虽然在这步看来是否交换没什么区别,但是如果 i 和 j 之间有元素,就有区别了,比如 Step7.

Step2.

指针 j 指向 2,而 2 应该放在 [i, j) 区间内,所以 j++.

Step3.

指针 j 指向 3,而 3 应该放在
(k, array.length-1] 区间内,所以这里
j 和 k 指向的元素交换一下,并且 k–.

注意这里就不能 j– 了,因为新换回来的元素还没瞧呢,不知道它是几。

Step4.

指针 j 指向 2,同 Step2,直接移动指针 j 即可。

Step5.

继续移动指针 j。

Step6.

同 Step3.

Step7.

这一步就很明显看出来了,
由于 1 应该放在 [0,i) 区间,所以这里把指针 i,j 所指向的元素交换一下,并且 i++, j++.

这样未排序区间为空,我们就排好了~

时间复杂度

这个算法的 bottle neck 就在这个 while loop 里了,每次循环是 O(1),总共是 O(n).

空间复杂度

O(1)

今天的题目就到这里啦,你们还喜欢吗?还有什么想让我写的可以留言告诉我哦~

五月的最后一天,五月天只会迟到,但不会缺席。

看着今日的线上演唱会,让我想起上一次去五月天的演唱会,还是三年前他们来纽约的「人生无限公司巡回演唱会」,翻了翻朋友圈,历历在目。

新的一周,新的一月,祝大家节日快乐吖~

愿你我走出半生,归来仍是少年。

正文完
 0