如何在O(n)时间内计算0,1,2,...,n中设置的1位数？

Question

这是一个面试问题.原始问题问:

给定正整数N,计算从0到N的每个整数中的1的数量,并以大小为N + 1的数组返回计数.在O(n)时间做.

一个例子是:

给定7,然后返回[0,1,1,2,1,2,2,3]

当然,最简单的方法是为每个整数创建一个计数1的循环,但这将是O(kn)时间,其中k是整数的大小(以位为单位).所以要么有办法在O(1)时间内计算一个整数的1,或者有一种方法可以直接生成从0到N的计数.我确定这两种方法都存在,但无法弄清楚无论是.

Answer 1

这是一个很好的小观察,你可以用它在时间O(n)做到这一点.想象一下,你想知道在数字k中设置了多少1位,并且你已经知道在数字0,1,2,...,k-1中设置了多少1位.如果你能找到一种方法为了清除在数字k中设置的任何1位,你会得到一些较小的数字(让我们称之为m),然后在k中设置的位数将等于1加上设置的位数米 因此,假设我们可以找到一种方法来清除数字k中的任何 1位,我们可以使用此模式来解决问题:

result[0] = 0  // No bits set in 0
for k = 1 to n:
    let m = k, with some 1 bit cleared
    result[k] = result[m] + 1

有一个着名的有点蠢事

 k & (k - 1)

通过清除在数字k中设置的最低1位形成的数字,并且在时间O(1)中进行,假设机器可以在恒定时间内进行按位运算(这通常是合理的假设).这意味着这个伪代码应该这样做:

result[0] = 0
for k = 1 to n:
    result[k] = result[k & (k - 1)] + 1

这样O(1)每个数字O(n)的总工作时间,所以完成的总工作量是O(n).

这是一种不同的方法.例如,想象一下,您知道数字0,1,2和3中的位数.您可以通过注意数字来生成数字4,5,6和7的位数.这些数字具有按位表示形式,这些表示形式是通过取0,1,2和3的按位表示形式然后前置1.然而,如果您知道位数为0,1,2,3,4,5,如图6和7所示,你可以通过在每个较低的数字前加1位来形成它们,从而产生8,9,10,11,12,13,14和15的位数.这就产生了这种伪代码,为简单起见,假设n的形式为2 ^k - 1,但可以很容易地适用于一般的n:

result[0] = 0;
for (int powerOfTwo = 1; powerOfTwo < n; powerOfTwo *= 2) {
    for (int i = 0; i < powerOfTwo; i++) {
        result[powerOfTwo + i] = result[i] + 1;
    }
}

这也在时间O(n)中运行.要看到这一点,请注意,在此处所有循环的所有迭代中,数组中的每个条目都只写入一次,完成O(1)工作以确定应该将哪个值放入该插槽的数组中.