LeetCode-75. 颜色分类(荷兰国旗问题)
75. 颜色分类
【题目】:
【代码】:
方法1:荷兰国旗问题
荷兰国旗包含三种颜色:红、白、蓝。
有三种颜色的球,算法的目标是将这三种球按红、白、蓝顺序正确地排列。我们可以将数组分为三个部分:等于红色0、等于白色1、等于蓝色2。遍历数组,遇到0前移,遇到1数组不动,继续遍历,遇到2后移。
分析可参考:https://www.cnblogs.com/gnuhpc/archive/2012/12/21/2828166.html
图片来自维基百科。
效果:
方法2:统计红白蓝三色球(0,1,2)的个数,重构数组,时间复杂度:O(n)