c++ - 如何在小于线性时间的情况下对位数组中的位进行分区

Question

这是我最近遇到的一道面试题。

---

给定一个由 1 和 0 组成的数组，找到一种方法来就地 对位进行分区，以便 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);    }

但是，面试坚持有一个次线性的解决方案。这让我苦思冥想，但仍然没有得到答案。

任何人都可以帮助解决这个面试问题吗？

UPDATE:看到SO中的回复说问题无法在次线性时间内解决，我可以确认我最初的想法是不能有次线性的解决方案。

会不会是面试官在耍花招？

Answer 1

我不明白怎么会有比线性时间更快的解决方案。

想象一个全为 1 的位数组。任何解决方案都需要在声明该数组已分区之前检查该数组中的每一位。检查每一位都需要线性时间。