1

我了解 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;
    }
}
}
4

1 回答 1

1

这绝对是O(n)O(nk)只要颜色的数量k是恒定的,就很容易做到。

对于类似于三路分区(荷兰国旗问题)的算法,我建议使用两遍算法。例如,在第一遍时,我们将0所有的 、 和 视为左侧部分,1并将23视为中间部分,并4视为右侧部分。在第二遍中,我们在边界处跳过0s 和s,并对s、s 和s4进行三向划分。请注意,结果是一个稳定的分区:每次通过时,相同元素的顺序保持不变。123

于 2018-05-17T04:03:54.670 回答