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

Question

问题来源于 编程面试要素：

给定一个大小为 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)时间内解决它吗？

- Jihed Amine

---

密切相关，荷兰国旗问题。 - thefourtheye

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

- Benjy Kessler

---

非常好！干净且高效！ - Jihed Amine

OP只需要保留真实值之间的相对顺序。 - Benjy Kessler

@Ricky 不要陷入这个圈套。无论如何，我们正在讨论Java，因此int（和数组大小）限制为32位，因此假设单个数字的操作和内存都是恒定时间，这既更有用又更简单。 - Voo

@Ricky 是的，这完全取决于您想使用哪种计算模型。事实证明，对于大多数算法，假设单个整数需要O(1)空间和O(1)时间进行简单算术运算是最有用的。因此，对于许多问题，假设reduce(arr, (t, e) -> t + e)为O(n)是完全可以的，尽管是的，您也可以选择m位大小为O(nm)，对于某些问题，这确实会产生很大的差异。 - Voo

如果递减不是内联发生的话，我会认为这是一种改进。这样做可以减少思考量，减少混淆。 - jpmc26

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

- Jared Burrows

---

该数组包含具有布尔字段的对象。整个对象需要被交换到新位置，而不仅仅是真值。 - Edward Doolittle

假设有一个由 n 个对象组成的数组 A，每个对象都有布尔值键。 - Edward Doolittle

@EdwardDoolittle 你说得对，我把问题标题读成了 boolean[]。 - Jared Burrows

它不保留顺序。我知道布尔值太过原始，无法看到不保留真实元素顺序的后果。 - Grzegorz Górkiewicz

Answer 3

假设数组索引从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)。这种方法可以保留假和真值之间的顺序。（该方法将真值放在前面，您可以根据需要进行更改）。

- advocateofnone

---

是的，顺序被保留了，但数组以真值开头而不是假值。（也许在O（n）时间内将其翻转就可以解决问题？） - Jihed Amine

反过来做，而不是从前往后。 - rici

改为仅测试假值而非真值。将if A[i] is true改为if A[i] is false。 - Ubica

@ubica：不对。这样会保留错误键入元素的顺序，同时将它们放在开头。你想要的是保留正确键入元素的顺序，同时将它们放在末尾。 - rici

将 true 替换为 false。这不会重新排列某些 true 的值吗？你需要插入而不是交换，对吧？ - Edward Doolittle

Answer 4

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

- Anon84

---

虽然这段代码可能回答了问题，但提供有关它如何以及/或为什么解决问题的附加上下文将改善答案的长期价值。 - mech

Answer 5

观察到对于固定的k，2k是O(1)，而2n是O(n)。构建第二个数组，并将源数组中的元素复制到目标数组中，在一端添加键为false的元素，在另一端添加键为true的元素。您可以扫描一次数组以找出边界必须在哪里。

- Charlie Martin

---

OP希望使用O(1)的额外空间。如何在O(1)的空间中创建一个额外的数组？k是指什么？ - Benjy Kessler