在O(n)时间内估算数组元素的频率

Question

我想标题可能有点误导，但我想不出更好的标题。

我有一个数组A []，除了一个元素外，其余所有元素出现的次数都是15的倍数，例如2出现30次，3出现45次。 但有一个元素出现了x次，其中x不是15的倍数。 如何打印数字x。 我正在寻找一种线性解决方案，而不使用哈希表。

谢谢。

- 0fnt

---

啊，我正想说哈希表呢！ :) - leppie

@leppie 如果你想要一个保证 O(1) 的哈希表，那么它的大小将会是 2^32，这是不切实际的。否则你就无法达到保证的 O(n)。 - Andrey

处理 n 个元素中出现 m 次的面试问题。 - Nabb

Answer 1

这里曾经有一个类似的问题在StackOverflow上，但我找不到了。

让我们使用3代替15，因为这样会更容易，而且我认为它是完全等价的。序列将是4、5、4、5、3、3、4、5，在二进制中是100、101、100、101、11、11、100、101。

可以这样做：对数字中最低有效位的所有值求和，并对3取余数（原来是15）：

bit1 = (0 + 1 + 0 + 1 + 1 + 1 + 0 + 1) % 3 = 5 % 3 = 2 != 0

如果它不等于0，则该位在我们要查找的数字中等于1。现在让我们继续下一步：

bit2 = (0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) % 3 = 2 % 3 = 2 != 0

bit3 = (1 + 1 + 1 + 1 + 0 + 0 + 1 + 1) % 3 = 6 % 3 = 0 == 0

所以我们有bit3 == 0，bit2 != 0，bit1 != 0，即011。转换为十进制：3。

空间复杂度为O(1)，时间复杂度为O(n * BIT_LENGTH_OF_VARS)，其中BIT_LENGTH_OF_VARS为byte时为8，int时为32等等。因此它可能很大，但常数不影响渐近行为，O(n * BIT_LENGTH_OF_VARS)实际上是O(n)。

就是这样！

- Andrey