如何以小于线性的时间对位数组中的位进行分区

Question

这是我最近面临的一个面试问题.

---

给定1和0的数组,找到一种方法来对位进行分区,in place以便将0组合在一起,并将1组合在一起.1是在0之前还是0在1之前是无关紧要的.

示例输入是101010101,输出是111110000或000011111.

在不到线性的时间内解决问题.

使问题更简单.输入是一个整数数组,每个元素为1或0.输出是相同的整数数组,整数分区很好.

---

对我来说,这是一个简单的问题,如果它可以在O(N)中解决.我的方法是使用两个指针,从数组的两端开始.增加和减少每个指针; 如果它没有指向正确的整数,则交换两者.

    int * start = array;
    int * end = array + length - 1;

    while (start < end) {
        // Assume 0 always at the end
        if (*end == 0) {
            --end; 
            continue;
        }

        // Assume 1 always at the beginning
        if (*start == 1) {
            ++start; 
            continue;
        }

        swap(*start, *end);
    }

然而,采访坚持认为存在一个亚线性解决方案.这让我苦苦思索,但仍未得到答案.

有人可以帮忙解决这个面试问题吗？

更新:看到SO中的回复表明问题无法在次线性时间内解决,我可以确认我原来的想法,即不存在子线性的解决方案.

面试官有可能发挥作用吗？

Answer 1

我看不出比线性时间更快的解决方案.

想象一下所有1的位数组.任何解决方案都需要在声明它已经被分区之前检查该数组中的每一位.检查每一位需要线性时间.

Answer 2

这是不可能的.在不到线性时间内完成它意味着您不会查看每个数组元素(如二进制搜索).但是,由于无法在不查看数组的任何元素的情况下知道它是什么,因此必须至少查看一次每个数组元素.

您可以使用查找表来加快速度,但O(n/8)仍然是O(n),因此访问者错了或者您误解了问题.