布尔数组在O(1)空间和O(n)时间内重新排序

Question

问题取自编程访谈要素:

给定具有布尔值键的n个对象的数组A,对数组重新排序,以便首先出现具有错误键的对象.具有键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)时间内解决它？

Answer 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)记忆中运行.

Answer 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]
}