专栏首页小浩算法漫画:常考的荷兰国旗问题你还不会吗?(初级)

漫画:常考的荷兰国旗问题你还不会吗?(初级)

今天是小浩算法 “365刷题计划” 第93天 。为大家分享经典的荷兰国旗问题。最近折腾了挺多事情,状态有点乱糟糟的。这两天刚刚调整好,全副武装,横戈马上行!

01

PART

荷兰国旗问题

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

荷兰国旗问题:现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。

这个问题之所以叫荷兰国旗,是因为我们可以将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。

大概就是这么个意思:

02

PART

题解分析

这道题很经典,很高频。

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

改成这样:

好了,这道题结束了。O(∩_∩)O


Emmmm....不开玩笑,现在我们讲解如何完成这个过程。

首先,用脚趾头都可以想到的是,最终排序完成后的数组是分成三份的:

红-白-蓝

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

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

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

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

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

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

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

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

总结一下:

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

大概就是这么一个分析过程,代码其实就很简单了(注意体会一下下面两种代码 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--
        }
    }
}

Java版本:略

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

03

PART

啰嗦一下

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

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

我觉得我讲的还是可以的。大家要是认为ok的话,给我来个转发吧~感谢!今天的题目到这里就结束了,如果想看其他面试题相关内容的,可以看:

漫画:知乎面试题(旋转数组最小值Ⅰ - 基础版)

漫画:知乎面试题(旋转数组最小值Ⅱ - 进阶版)

漫画:美团面试题(TOPK:求第K个最大的元素)

漫画:腾讯面试题(面试官问我会不会修供暖器,我说没问题)

漫画:位运算技巧整理汇总+一道被嫌弃的题目

如果你问我对学习算法有什么建议,这篇文章是必看的:

漫画:小白为了面试如何刷题?(呕心沥血算法指导篇)

漫画:呕心泣血算法指导篇(真正的干货,怒怼那些说算法没用的人)

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩
  • 漫画:经典鹅厂面试题(4sum - nSum)

    第18题:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + ...

    程序员小浩
  • 漫画:美团面试题(TOPK:求第K个最大的元素)

    这个题目的变形很多,比如找 "前 K 个高频元素"、 "数据流中的第K大元素" 、"最接近原点的 K 个值" 等等等等。

    程序员小浩
  • 【python-leetcode448-循环排序】找到所有数组中消失的数字

    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    绝命生
  • python-快速排序

    核心思想:取一个初始值,将数组中比该值小的放在其左边,比其大的放在右边, 再对左、右子数组进行相同操作,直到数组排好序。

    绝命生
  • Leetcode Golang 75. Sort Colors.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • 【python-leetcode287-循环排序】寻找重复的数

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个...

    绝命生
  • Leetcde Golang 26. Remove Duplicates from Sorted Array.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88902453

    anakinsun
  • 【leetcode】15:三数之和

    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组...

    帅地
  • 数据结构算法操作试题(C++/Python)——四数之和

    数据结构算法操作试题(C++/Python):数据结构算法操作试题(C++/Python)——目录

    莫斯

扫码关注云+社区

领取腾讯云代金券