在O（n）时间估计一个数组元素的频率

Question

我想标题可能有点误导，但我想不出一个更好的。 我有一个数组A []，其中的所有元素都出现了一些倍数为15的倍数，例如2次发生30次，3次发生45次。但是一个元素会出现x次，其中x不是15的倍数。如何打印数字x。我正在寻找一个没有散列表的线性解决方案。

谢谢。

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 == 8为字节，BIT_LENGTH_OF_VARS == 32对于int等，因此，它可以很大，但常数不影响渐近性和O(n * BIT_LENGTH_OF_VARS)真的O(n)。

就是这样！