java - 在 O(1) 空间和 O(n) 时间中重新排序的 boolean 数组

Question

问题出自Elements of Programming Interviews :

给定一个包含 boolean 值键的 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 < 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) 内存中运行。