这道荷兰旗问题，我面试时遇到三次！

深藏阁楼爱情的钟 2022-12-17 08:41 99阅读 0赞

> 大家好，我是不会写代码的小浩。**今天为大家分享经典的荷兰国旗问题**。

## 01、题目示例 ##

> "荷兰国旗问题" 是计算机科学中的一个经典题目，它是由Edsger Dijkstra提出的。荷兰国旗由红、白、蓝三色组成。

<table> 
 <thead> 
  <tr> 
   <th>荷兰国旗问题：现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。</td> 
  </tr> 
 </tbody> 
</table>

大概就是这么个意思：

![format_png][] ![format_png 1][]

## 02、题解分析 ##

> 这道题很经典，很高频。

便于分析，我们把上面的图稍微改一下：

![format_png 2][]

改成这样：

![format_png 3][]

我们很容易可以想到的是，最终排序完成后的数组是分成三份的：

**红-白-蓝**

那总共就三个颜色，我们要区分开来，是不是最少需要两条分隔线？A线的左侧为0，右侧为1。B线的左侧为1，右侧为2。

![format_png 4][]

但是刚开始的时候，红-白-蓝 三色是乱序的，所以此时的两条线我们是不是可以看成在最两侧？

![format_png 5][]

那我们剩下的是不是只需要把 A线 和 B线 间的数据维护成满足 AB 线的规则就可以了？那要维护 AB 线间的数据，是不是至少你得遍历下 AB 线间的数据？

![format_png 6][]

我们从 C 位置处开始，**我们发现此时 C 等于0。是不是意味着，我们应把这个元素放到 A 的左侧，所以我们移动 A线。当然，我们也需要移动一下 C 的位置。（CASE-1）**

![format_png 7][]

然后我们发现**新的 C 位置处等于2，那是不是说明这个元素应该位于 B 的右侧。所以我们要把该位置的元素 和 B位置处的元素进行交换，同时移动B。(CASE-2)**

![format_png 8][]

但是这里要注意，**C 交换完毕后，C 不能向前移**。因为C指向的元素可能是属于前部的，若此时 C 前进则会导致该位置不能被交换到前部。继续向下遍历。

![format_png 9][]

有意思了，**我们发现 C 指向位置处等于1。有没有发现这种本身就满足规则了？所以我们忽略就可以了。（CASE-3）** 继续移动 C。

![format_png 10][]

主要就这三种 CASE，我们把剩下的图都绘制出来：

![format_png 11][] ![format_png 12][] ![format_png 13][] ![format_png 14][]

**总结一下：**

*  1）若遍历到的位置为0，则说明它一定位于A的左侧。于是就和A处的元素交换，同时向右移动A和C。
 *  2）若遍历到的位置为1，则说明它一定位于AB之间，满足规则，不需要动弹。只需向右移动C。
 *  3）若遍历到的位置为2，则说明它一定位于B的右侧。于是就和B处的元素交换，交换后只把B向左移动，C仍然指向原位置。（因为交换后的C可能是属于A之前的，所以C仍然指向原位置）

大概就是这么一个分析过程，代码其实就很简单了：

python 版本：

//py3 
    class Solution: 
        def sortColors(self, nums: List[int]) -> None: 
            a = c = 0 
            b = len(nums) - 1 
            while c <= b:
                if nums[c] == 0: 
                    nums[a], nums[c] = nums[c], nums[a]
                    a += 1
                    c += 1
                elif nums[c] == 2:
                    nums[c], nums[b] = nums[b], nums[c]
                    b -= 1
                else:
                    c += 1

go 版本：

//go 
    func sortColors(nums []int) { 
        a := 0 
        b := len(nums) - 1 
        for c := 0; c <= b; c++ { 
            if nums[c] == 0 { 
                nums[c], nums[a] = nums[a], nums[c] 
                a++
            }
            if nums[c] == 2 {
                nums[c], nums[b] = nums[b], nums[c]
                c--
                b--
            }
        }
    }

执行结果：

![format_png 15][]

## 03、总结 ##

> 这道题目限制了最大数为 3999，时间复杂度也就被限制成了O(1)。（这句话忽略！上次的文章忘记删除了。。）

好吧，基本就是这样了。这道题目在 leetcode 上对应的是：

![format_png 16][]

我觉得我讲的还可以。大家要是认为 ok 的话，给我来个赞吧！

--------------------

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 1]• [计算机专业的学生怎样练习编程才能把编程学精通？][Link 2]• [为什么 MySQL 使用 B+ 树][MySQL _ B_]• [一道简简单单的字节跳动算法面试题][Link 3]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 17][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sSmd4OXU1bm0wRVNocnRPY2lhWjBXSjhMbUg5a3NydFdlMUJoQVpOVUtPUTQ0aWFLN3Rxa2lhaWM0eXVqTVZUNzBKN1Z5M1MwYW9xR3hIZmFZZXJSbjQyRkEvNjQw?x-oss-process=image/format,png
[format_png 1]: /images/20221122/9cc25cab50df49469d06900d855b8a68.png
[format_png 2]: /images/20221122/9e2670101cec4144a52b5f2d3d66a57d.png
[format_png 3]: /images/20221122/ec51b43f7e824d5b8ac24ea31aae57b0.png
[format_png 4]: /images/20221122/00b0f33e6523425f80c6ba0214cad61b.png
[format_png 5]: /images/20221122/753b0b96bba3474a8398c96fec0e17dc.png
[format_png 6]: /images/20221122/41f19354be9944b08bd8aa10ce394ed8.png
[format_png 7]: /images/20221122/443ae3e2cc2a4cef998918d2777d7b05.png
[format_png 8]: /images/20221122/a676b91568b146eeacc27a2dc37b74b6.png
[format_png 9]: /images/20221122/08630229b9cf465a9a8c0f85105caafd.png
[format_png 10]: /images/20221122/ffb47a67f9034c269d3a09d456c1e304.png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sSmd4OXU1bm0wRVNocnRPY2lhWjBXSjhMbUg5a3NydFdQRHlLaWJzVnlEM3N0aWJKQXQ3SGp5NVh4d2drYVBWekFBY0RmaDlGUUJUNjduWDZBT3JWaDhXZy82NDA?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sSmd4OXU1bm0wRVNocnRPY2lhWjBXSjhMbUg5a3NydFc2Y0VTTDd0TkFNaWN0VDlMNVNxQm9ZYjJkYUhBVFM5OFRsQTRnZUx2aDA0NHl3NTlyMmpXNVd3LzY0MA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9sSmd4OXU1bm0wRVNocnRPY2lhWjBXSjhMbUg5a3NydFdXVTViWFBEM2RpY0h1T3JwVTIzTDRnS2RVdUN1V1NpYU5XVnZTVll4UGpvRkRpY1ZTbHJTZ3p6aWF3LzY0MA?x-oss-process=image/format,png
[format_png 14]: /images/20221122/8a67adcb0a794c28a88ccbd1896b6d0b.png
[format_png 15]: /images/20221122/80bde266ddc1491daf99d11ca7c2783e.png
[format_png 16]: /images/20221122/647159fe6a0b4cba8fca9df74def7d53.png
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75efcd79fcf9c65ebb5070122b9705e18cb1c46b06c5eb3e299520ed4a25e327bc07bb4b&idx=2&mid=2247490158&scene=21&sn=12e587a361f0df072d2dc164c219a61e#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75aecd79fcb8b5f932c7ba5ed7a9e34a6c99f20bc129cef33774167d668e8745755d02ad&idx=1&mid=2247490095&scene=21&sn=baa0379b1ca62db17327a2cb825a1b24#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d87aacd7a0ebc3ada34a076d1fa3943ee24097966257132b1042b7a3e4debedc78f38c8cf&idx=1&mid=2247493675&scene=21&sn=6b501ef2032ab911f0a3519eb7397017#wechat_redirect
[MySQL _ B_]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e759ccd79fc8a73c77eacfd7c8b1391b08864e2e13fdf5a6e41e218a499d5a87ee12e4e6a&idx=2&mid=2247490077&scene=21&sn=56c52b385c98c7f0ad33c2621da101eb#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e767dcd79ff6b2733dd8905f188afb19eb400d5e644f5b5127f909ee7c3583786031f9c20&idx=2&mid=2247490044&scene=21&sn=bb3610dfedbb2e0c017c3ff3d5e4684b#wechat_redirect
[format_png 17]: /images/20221122/a086413373674097bef7112b4cd5f797.png