Boolean array reordering in O(1) space and O(n) ti

问题:

The problem is taken from Elements of Programming Interviews:

Given an array A of n objects with Boolean-valued keys, reorder the array so that objects that have the key false appear first. The relative ordering of objects with key true should not change. Use O(1) additional space and O(n) time.

I did the following, it preserves the relative ordering of objects with key true and uses O(1) additional space, but I believe its time complexity is 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++;
    }
  }
}

Anyone has an idea on how to solve it in O(n) time?

回答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]);
  }
}

After every iteration all elements after lastTrue are true. No two true elements are swapped because if there was a true element between i and lastTrue it would have been encountered already and moved behind lastTrue. This runs in O(n) time and O(1) memory.

回答2:

Java Code - if you are using a Boolean[] - objects:

Time - O(1), Space - O(1)

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

Time - O(N), Space - 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 Test Case:

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 Code - if you are using a boolean[] - primitives:

Time - O(N), Space - 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 Test Case:

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:

Let the array have 0 based index and let it have n elements. Then you can do the following ( pseudo code below )

     // 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

Time complexity is O(n) and extra space is only used for two variables i and j so memory is O(1). This way ordering is preserved amongst false and true values. ( This method puts true ones first you can change it according to your requirement ).

回答4:

Observe that 2k for fixed k is O(1), and 2n is O(n). Construct a second array, and copy elements from the source array to the target array, adding elements with key false at one end and key true at the other. you can scan the array once to find out where the boundary must be.

回答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;
    }