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

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.

给定具有布尔值键的n个对象的数组A，对数组重新排序，以便首先出现具有键false的对象。具有键true的对象的相对排序不应更改。使用O（1）额外空间和O（n）时间。

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!).

我做了以下操作，它保留了对象为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++;
    }
  }
}

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

任何人都知道如何在O（n）时间内解决它？

5 个解决方案

#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.

每次迭代后，lastTrue之后的所有元素都为true。没有交换两个真正的元素，因为如果i和lastTrue之间存在真正的元素，那么它已经遇到并移到了lastTrue之后。这在O（n）时间和O（1）存储器中运行。

#2

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

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

时间 - 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;
}

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

时间 - 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 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)

时间 - 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 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 )

让数组有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

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 ).

时间复杂度为O（n），额外空间仅用于两个变量i和j，因此存储器为O（1）。这种方式在虚假和真实值之间保持排序。 （这种方法首先是真的，你可以根据你的要求改变它）。

#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.

观察到固定k的2k是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;
    }