Я понимаю проблему DNF для 3 цветов.Предположим, я хочу увеличить количество цветов до 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;
}
}
}