algorithm - 荷兰国旗
问题描述
我了解 3 种颜色的 DNF 问题。假设我想将颜色数量扩展到 5 (0,1,2,3,4),我还能得到 O(n) 复杂度吗?
所以我认为我们有 5 个区域,其中 2 个是未知区域。但是如何实现呢?我可以轻松地将 3 种颜色的算法扩展到 5 种颜色吗?
void sort012(int a[], int arr_size){
int lo = 0;
int hi = arr_size - 1;
int mid = 0;
while (mid <= hi){
switch (a[mid]){
case 0:
swap(&a[lo++], &a[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(&a[mid], &a[hi--]);
break;
}
}
}
解决方案
这绝对是O(n)
:O(nk)
只要颜色的数量k
是恒定的,就很容易做到。
对于类似于三路分区(荷兰国旗问题)的算法,我建议使用两遍算法。例如,在第一遍时,我们将0
所有的 、 和 视为左侧部分,1
并将2
和3
视为中间部分,并4
视为右侧部分。在第二遍中,我们在边界处跳过0
s 和s,并对s、s 和s4
进行三向划分。请注意,结果是一个稳定的分区:每次通过时,相同元素的顺序保持不变。1
2
3
推荐阅读
- joomla - Joomla - 如何为不在视图中的组件文件创建覆盖
- java - 匹配最后一个空格之前的任何字符
- android - 如何使用 Kotlin 通过 Dagger 2.11 注入 SP?
- google-sheets - 拆分和转置数组
- r - “filename.rdata”文件探索和转换为 CSV
- javascript - Laravel Mix + Vue-Loader 15
- python - 遇到同时连接到多个设备的多线程问题
- swift - TwitterKit 以模态方式关闭视图控制器
- html - 标题中溢出的背景颜色
- javascript - setCustomValidity 不是函数