我在面试中被问到了问题。我很接近解决方案,但不幸的是没有解决。
假设我们有一个序列,其中包含 N个 数字long。而且我们可以肯定地知道,在该序列中,每个数字确实发生了 n 次,除了一个数字发生了 m 次( 0 < m < n )。我们如何通过 O(N)个 运算和 O(1)个 额外的内存来找到该数字?
long
对于最简单的情况(当 n = 2 和 m = 1时 ),我们要做的只是对xor序列中的每个数字进行累加。结果将等于所需的数字。但是我在尝试处理任意 m 和 n时 陷入困境。
xor
我将感谢实际的C ++解决方案。
编辑:我们知道先验 m 和 n 的实际值。
例。 我们知道 n = 3和 m =2。序列( N = 8 )是
5 11 5 2 11 5 2 11
在这种特殊情况下,正确答案是 2 ,因为它只出现两次。
您进行64次求和,每位求和一次,对于计算sum mod n的每个求和,此计算对于应在结果中设置的每个位返回m,对于不应该设置的每个位返回0。
示例: n = 3,m =2。list = [5 11 5 2 11 5 2 11]
5 11 5 2 11 5 2 11 sum of bit 0: 1 + 1 + 1 + 0 + 1 + 1 + 0 + 1 = 6 6 % 3 = 0 sum of bit 1: 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1 = 5 5 % 3 = 2 sum of bit 2: 1 + 0 + 1 + 0 + 0 + 1 + 0 + 0 = 3 3 % 3 = 0 sum of bit 3: 0 + 1 + 0 + 0 + 1 + 0 + 0 + 1 = 3 3 % 3 = 0
因此,仅设置了位1,这意味着结果为2。
优化实现:( 对实际问题也有用的技巧和注意事项) 值得注意的是,在数组上进行迭代时,执行速度将在某种程度上受到内存访问的限制,如果需要对每个元素执行多个操作,则是通常一次将所有元素一次执行一次最快,因此处理器只需要从内存中加载一次即可。关于内存和缓存的有趣博客文章。
可以将一个整数中的多个位相加,而不是应用64个不同的位掩码来单独获得每个位,例如可以仅使用4个位掩码,每个掩码提取16位,且每个位之间有3位空格,只要没有发生溢出时,正常的加法运算将完全像处理16个4位整数一样工作,因此此方法将对15个数字起作用。以这种方式处理15个数字后,结果必须添加到能够容纳更大整数的存储中(可以是8个64位整数,每个容纳8个8位整数,当然必须依次将它们清空为更大的整数,依此类推。 )。 结果是,不必为每个值执行64个位掩码,63个移位和64个加法运算,就只需要执行4个位掩码,3个移位和4个加法运算,再加上每15个值8个掩码,4个移位和8个加法运算,以及每255个值。 16个位掩码,8个移位和16个加法等
可视化:( 使用16位整数求和4x4位整数)
1000 1000 1000 1000 + 1000 0000 0000 1000 + 0000 0000 0000 1000 + 1000 1000 0000 0000 + 1000 0000 1000 0000 + 0000 0000 1000 1000 = 0010 0100 1100 0010
无论您认为这是4列4位整数还是1列16位整数,结果都是相同的,只要4位整数不溢出,这是正确的。