布尔数组在O（1）空间和O（n）时间内重新排序
问题取自编程访谈要素 ：
给定具有布尔值键的n个对象的数组A，对数组重新排序，以便首先出现具有键false的对象。 具有键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 lastFalseIdx) { swap(a, falseIdx, falseIdx-1); falseIdx--; } lastFalseIdx++; } } } 任何人都知道如何在O（n）时间内解决它？
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之后的所有元素都为true。 没有交换两个真正的元素，因为如果i和lastTrue之间存在真正的元素， lastTrue它已经遇到并移到了lastTrue 。 这在O(n)时间和O(1)存储器中运行。
Java代码 – 如果您使用Boolean[] – 对象：
时间 – O（1），空间 – O（1）
public static 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] }
让数组有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) 。 这种方式在虚假和真实值之间保持排序 。 （这种方法首先是真的，你可以根据你的要求改变它）。
观察到固定k的2k是O（1），2n是O（n）。 构造第二个数组，并将元素从源数组复制到目标数组，在一端添加键为false元素，在另一端键入true 。 你可以扫描一次数组，找出边界必须在哪里。
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; }