arrays - 在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，则该位数等于我们要查找的位数。现在让我们转到下一个:
bit2 = (0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) % 3 = 2 % 3 = 2 != 0bit3 = (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)。

就是这样!