荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示:
假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况:
需求是:把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,我们把这类问题称作荷兰国旗问题。
荷兰国旗问题抽象为如下描述:
给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边,要求额外空间复杂度为O(1),时间复杂度为O(n)