Сортировка booleans, O (N) time, O (1) space

Question

Для домашнего задания меня попросят отсортировать массив bools с использованием метода, который использует O (1) пространство и O (N) временную сложность. Могут ли предлагаться какие-либо подсказки? Я думал о чем-то по сводному методу алгоритма быстрой сортировки. -Спасибо!

Answer 1

1. Держите указатель спереди и сзади.
2. проверить текущий передний индекс, если это ложный увеличиваем передний индекс
3. , если это правда своп с индексом обратно и уменьшает индекс назад
4. продолжить с шагами 2 и 3 до передних и задних индексов равны другие

Answer 2

Если у вас есть массив булевых, вы можете просто считать (ложные или ) значений верно. Предположим, что этот результат равен k. Затем вы устанавливаете первые k элементов массива на true, а остальные false.

Этот алгоритм перебирает массив в два раза (так что имеет временную сложность O (N)), и использует только один счетчик, поэтому пространство требуется O (1).

Answer 3

Поскольку логические значения имеют только два возможных значения, вы можете просто подсчитать «истинные» и «ложные» s и изменить исходный массив на месте, чтобы сначала вы поместили в него соответствующее количество значений false, затем заполните остальные true. Это O(n) во времени и O(1) в космосе, если требуется. код C следующим образом:

void sortbool(int *b, size_t n) 
{ 
    size_t k = 0; 
    for (size_t i = 0; i < n; i++) { 
      if (!b[i]) 
        k++; 
    } 

    for (size_t i = 0; i < n; i++) { 
      b[i] = !(i < k); 
    } 
}