代码之家 › 专栏 › 技术社区 › SiLent SoNG

如何在少于线性时间的位数组中划分位

c++

SiLent SoNG · 技术社区 · 16 年前

给定一个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 &lt 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);
    }

然而,采访坚持认为有一个次线性的解决方案。这让我费劲思考,但仍然没有得到答案。

更新 :看到答复中这样说问题不能在次线性时间内解决,我可以证实我原来的想法,即不可能有次线性时间的解决办法。

有没有可能面试官在耍花招?

9 回复 | 直到 16 年前

Brandon Bodnar 16 年前

假设一个位数组都是1。任何解决方案都需要在声明数组已分区之前检查数组中的每一位。检查每一点都需要线性时间。

Gabe Timothy Khouri 16 年前

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

你可以使用查找表来加快速度,但是O(n/8)仍然是O(n),所以要么面试官错了,要么你误解了问题。

user295520 16 年前

如果你有足够的内存,它可能比线性时间更快,可以在O(1)中完成

使用您的示例,在索引341(101010101)处存储值496(11111 0000)。

GManNickG 16 年前

也许这种混乱来自于“线性时间不足”。例如,这个解决方案计算位的数量,这使得一个掩码包含那么多位。当有未计数的位时,它只计数位:

// from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
unsigned count_bits(unsigned pX)
{
    unsigned result;
    for (result = 0; v; ++result)
    {
        pX &= pX - 1;
    }

    return result;
}

unsigned n = /* the number */;

// r contains 000...111, with number of 1's equal to number of 1's in v
unsigned r = 1 << count_bits(n);

即使这样可以最小化要计数的位数,它仍然是线性的。所以,如果这就是所谓的“次线性”的意思,那就对了。

Swiss 16 年前

从技术上讲,您可以将阵列的每个元素发送到单独的处理器,然后在不到线性时间内完成。如果你有N个处理器,你甚至可以在O(1)时间内完成!

Naveen 16 年前

正如其他人所说,我不相信这能在少于线性时间内完成。对于线性时间解决方案,您可以使用STL算法代替自己的循环,如下所示:

int a1[8] = {1,0,1,0,1,0,1,0};
std::fill(std::remove(a1, a1+8, 0), a1+8, 0);

Vite Falcon 16 年前

好。。它可以做'小于线性'的时间(厚脸皮的方法)。

if(n % 2)
{
   // Arrange all 1's to the right and DON'T check the right-most bit, because it's 1
}else{
   // Arrange all 0's to the right and DON'T check the right-most bit, because it's 0.
}

Jack V. 16 年前

对我来说,最可能的解释是:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
他们用“次线性”来表示“少于n次运算”,而不是少于O(n)。但即便如此,出于下面列出的同样原因,这似乎也是不可能的。
这个问题还有另一个误解
否则问题就错了,因为必须检查数组的所有元素才能确定答案,这至少是n次运算。

user223264 user223264 15 年前

如果您假设并行度的增长速度比问题大小的增长速度慢,那么在并行处理器之间分割这项工作的代价是N/M(或O(N))。在过去的十年左右,并行性(通过GPU)比典型的问题规模增长得更快,而且这一趋势在未来几年内还将继续。对于一类广泛的问题,假设“无限并行性”或者更准确地说,“并行性大于任何预期的问题大小”是有指导意义的,因为随着时间的推移,gpu和云计算的进步提供了这样一种东西。

假设无限平行