高频面试考题:荷兰旗问题
source link: https://segmentfault.com/a/1190000022800506
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
荷兰旗问题又称三色排序,或者彩虹排序,
因为荷兰旗就三种颜色嘛,那这道题的问题就是给你三种颜色,按照给定的顺序排好。
当然了,题目的问法各种各样,有的给数字,有的给字母,但本质都是一样的。
比如给你一个只含有三个数字的数组: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)
今天的题目就到这里啦,你们还喜欢吗?还有什么想让我写的可以留言告诉我哦~
五月的最后一天,五月天只会迟到,但不会缺席。
看着今日的线上演唱会,让我想起上一次去五月天的演唱会,还是三年前他们来纽约的「人生无限公司巡回演唱会」,翻了翻朋友圈,历历在目。
新的一周,新的一月,祝大家节日快乐吖~
愿你我走出半生,归来仍是少年。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK