Буферное переупорядочение массива в O (1) пространстве и время O (n)

Проблема взята из Элементы программирования Интервью:

Учитывая массив A из n объектов с булевозначными ключами, измените порядок массива так, чтобы объекты, имеющие ключевое ложное значение, отображались первыми. Относительный порядок объектов с ключом true не должен меняться. Используйте O (1) дополнительное пространство и время O (n).

Я сделал следующее: он сохраняет относительный порядок объектов с ключом true и использует O (1) дополнительное пространство, но я считаю, что его временная сложность - O (n * n!).

public static void rearrangeVariant4(Boolean[] a) {
  int lastFalseIdx = 0;
  for (int i = 0; i < a.length; i++) {
    if (a[i].equals(false)) {
      int falseIdx = i;
      while (falseIdx > lastFalseIdx) {
        swap(a, falseIdx, falseIdx-1);
        falseIdx--;
      }
      lastFalseIdx++;
    }
  }
}

У кого-нибудь есть идея о том, как его решить в O (n) времени?

Ответы

Ответ 1

boolean array[n]; // The array
int lastTrue = n;
for (int i = n-1; i >= 0; --i) {
  if (array[i]) {
    swap(array[--lastTrue], array[i]);
  }
}

После каждой итерации все элементы после lastTrue верны. Два истинных элемента не заменяются, потому что если бы существовал истинный элемент между i и lastTrue, он уже встречался бы и перемещался бы за lastTrue. Это выполняется в O(n) времени и O(1) памяти.

Ответ 2

Java Код - если вы используете Boolean[] - объекты:

Время - O (1), Пробел - O (1)

public static <T> void swap(T[] a, int i, int j) {
    T t = a[i];
    a[i] = a[j];
    a[j] = t;
}

Время - O (N), Пробел - O (1)

public static Boolean[] getReorderBoolObjects(Boolean[] array) {
    int lastFalse = 0;

    for (int i = 0; i < array.length; i++) {
        if (!array[i]) {
            swap(array, lastFalse++, i);
        }
    }

    return array;
}

Spock Тестовый пример:

def "reorder bools - objects"() {
    given:
    Boolean[] b = [false, true, true, true, false, true]

    when:
    getReorderBoolObjects(b)

    then:
    b == [false, false, true, true, true, true]
}

Java Код - если вы используете примитивы Boolean[]:

Время - O (N), Пробел - O (1)

public static boolean[] getReorderBoolPrimitives(boolean[] array) {
    int falseCount = 0;
    for (final boolean bool : array) {
        if (!bool) {
            falseCount++;
        }
    }
    for (int i = 0; i < array.length; i++) {
        array[i] = i >= falseCount;
    }
    return array;
}

Spock Тестовый пример:

def "reorder bools - primitives"() {
    given:
    boolean[] b = [false, true, true, true, false, true]

    when:
    getReorderBoolPrimitives(b)

    then:
    b == [false, false, true, true, true, true]
}

Ответ 3

Пусть массив имеет индекс на основе 0 и пусть он имеет элементы n. Затем вы можете сделать следующее (псевдо-код ниже)

     // A[] is your array
     i = 0
     k = 0
     for i from 0 to n-1
          if A[i] is true
             swap A[i] and A[k]
             increment k

Сложность времени O(n), а дополнительное пространство используется только для двух переменных i и j, поэтому память O(1). Таким образом порядок сохраняется среди ложных и истинных значений. (Этот метод ставит истинные сначала, вы можете изменить его в соответствии с вашим требованием).

Ответ 4

Заметим, что 2k при фиксированном k равно O (1), а 2n - O (n). Создайте второй массив и скопируйте элементы из исходного массива в целевой массив, добавив элементы с ключом false на одном конце и клавишу true на другом. вы можете сканировать массив один раз, чтобы узнать, где граница должна быть.

Ответ 5

public static void rearrange(boolean[] arr) {
          int invariant = arr.length-1;
          for (int i = arr.length -1; i >= 0; i --) {
            if ( !arr[i] ) {
              swap( arr,i,invariant);
              invariant--;
            }
          }
    }
    private static void swap(boolean arr[] , int from ,int to){
        boolean temp = arr[from];
        arr[from]=arr[to];
        arr[to]=temp;
    }