我认为标题可能有点误导,但我想不出更好的一个.我有一个数组A [],其中一个元素除了其中一个元素出现的次数是15的倍数,例如2次出现30次,3次出现45次.但是一个元素出现x次,其中x不是15的倍数.如何打印数字x.我正在寻找没有哈希表的线性解决方案.
谢谢.
这里有类似的问题,在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).
而已!