一尘不染

处理N个事件中的M个

algorithm

我在面试中被问到了问题。我很接近解决方案,但不幸的是没有解决。

假设我们有一个序列,其中包含 N个 数字long。而且我们可以肯定地知道,在该序列中,每个数字确实发生了 n
次,除了一个数字发生了 m 次( 0 < m < n )。我们如何通过 O(N)个 运算和 O(1)个
额外的内存来找到该数字?

对于最简单的情况(当 n = 2 m = 1时
),我们要做的只是对xor序列中的每个数字进行累加。结果将等于所需的数字。但是我在尝试处理任意 m n时 陷入困境。

我将感谢实际的C ++解决方案。


编辑:我们知道先验 m n 的实际值。

例。 我们知道 n = 3和 m =2。序列( N = 8 )是

5 11 5 2 11 5 2 11

在这种特殊情况下,正确答案是 2 ,因为它只出现两次。


阅读 226

收藏
2020-07-28

共1个答案

一尘不染

您进行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位整数不溢出,这是正确的。

2020-07-28