Голландский национальный флаг - PullRequest
0 голосов
/ 16 мая 2018

Я понимаю проблему 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;
    }
}
}

1 Ответ

0 голосов
/ 17 мая 2018

Это определенно O(n): тривиально выполнимо в O(nk), пока число цветов k постоянно.

Для алгоритма, аналогичного трехстороннему разделению ( Задача голландского национального флага ), я бы предложил двухпроходный алгоритм. Например, при первом проходе мы воспринимаем 0 как левую часть, все 1, 2 и 3 как среднюю часть, а 4 как правую часть. На втором проходе мы пропускаем 0 s и 4 s на границах и делаем трехстороннее разбиение 1 s, 2 s и 3 s. Обратите внимание, что в результате получается стабильное разбиение: на каждом проходе порядок идентичных элементов остается неизменным.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...