布尔数组为O重新排序（1）空间和O（n）的时间 [英] Boolean array reordering in O(1) space and O(n) time

问题描述

这个问题是从编程的采访元素的：

由于n个对象的布尔值的键数组中的，重新排序阵列使其具有关键的虚假对象首先出现。 与关键的真实对象的相对顺序应该不会改变。使用O（1）额外的空间和O（n）的时间。

我做了下面，preserves与主要的真实对象的相对顺序，并使用O（1）额外的空间，但我相信它的时间复杂度为O（N * N！）。

 公共静态无效rearrangeVariant4（布尔[] A）{
  INT lastFalseIdx = 0;
  的for（int i = 0; I＆LT;则为a.length;我++）{
    如果（A [1] .equals（假））{
      INT falseIdx =我;
      而（falseIdx＆GT; lastFalseIdx）{
        交换（一个，falseIdx，falseIdx-1）;
        falseIdx--;
      }
      lastFalseIdx ++;
    }
  }
}
 

任何人对如何解决它在O（n）时间的想法？

解决方案

 布尔数组[N]; //数组
INT lastTrue = N;
的for（int i = N-1; I＆GT; = 0; --i）{
  如果（数组[我]）{
    掉期（数组[ -  lastTrue]，数组[I]）;
  }
}
 

每次迭代后后 lastTrue 所有元素都是如此。没有两个真正的要素交换，因为如果之间存在着真元我和 lastTrue 这本来已经遇到和感动背后 lastTrue 。这将运行在 O（N）时间和 O（1）内存。

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.

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

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?

解决方案

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.

这篇关于布尔数组为O重新排序（1）空间和O（n）的时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！