algorithm - 具有 16 位元素的 10000 数组，查找位集(无限 RAM)- Google 访谈

Question

这是我最近在 Google 采访中被问及的问题，我提供了一个涉及位移位且为 O(n) 的答案，但她说这不是最快的方法。我不明白，有没有一种方法可以在不必遍历提供的整个位的情况下对位集进行计数？

Answer 1

蛮力:10000 * 16 * 4 = 640,000 次操作。 (每个 16 位字的移位、比较、递增和迭代)

更快的方法:

我们可以构建表 00-FF -> 位数集。 256 * 8 * 4 = 8096 次操作

即我们构建了一个表，其中我们为每个字节计算了一些位集。

然后对于每个 16 位 int，我们将其分为上位和下位

for (n in array)
   byte lo = n & 0xFF; // lower 8-bits
   byte hi = n >> 8;   // higher 8-bits
   // simply add number of bits in the upper and lower parts 
   // of each 16-bits number
   // using the pre-calculated table
   k += table[lo] + table[hi];
}

迭代中总共有 60000 次操作。 IE。总共 68096 个操作。虽然它是 O(n)，但常数较少(少了约 9 倍)。

换句话说，我们计算每个 8 位数字的位数，然后将每个 16 位数字拆分为两个 8 位数字，以便使用预先构建的表格计算位集。