热门文章
 当前位置：技术文章 > 编程面试题 >

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 < a.length; i++) {
    if (a[i].equals(false)) {
      int falseIdx = i;
      while (falseIdx > 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元素，因为如果在它们之间存在一个true元素i，lastTrue它将已经被遇到并移到后面lastTrue。O(n)时间和O(1)内存都在运行。