处理N中的M次出现

Question

问题我是在面试时给出的.我接近解决方案,但不幸的是没有解决它.

假设我们有一个包含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,因为它只发生了两次.

Answer 1

对于计算总和mod n的每个总和,您为每个位执行64次求和,此计算为应在结果中设置的每个位返回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位整数不溢出就行.

Answer 2

编辑)好的,这种方法并不像我最初想的那样健全.电子商务的解决方案更简单,适用于n = 4,m = 2等情况.

我们可以推广xor方法来处理任意的m和n.我们首先需要选择一个基数b,使得gcd(n,b)= b,并且gcd(m,b)<b.由于奇数n /偶数m对满足基数2,因此标准二进制xor适用于这些对.

首先,我们将(a ^^ n)定义为na的平均值(a ^ a ^ ... ^ a),具有基数b的广义xor .例如,对于标准二进制xor,a ^^ 2 = 0.

我们需要定义我们的广义xor.我们想要的属性基本上与加法(交换性,相关性)相同,我们需要^^ b = 0.对于基本b表示中的每个数字,显而易见的解决方案是(x ^ y)=(x + y)%b(说服自己这是有效的,并且与基数2的二进制xor相同).然后,我们只是将它应用于序列中的所有数字,最后得到结果= s ^^(m%b),其中s是特殊数字. 最后,我们需要将'xor'ed base b数恢复为预期数.我们可以简单地为i = 0..b-1计算i ^^(m%b),然后查找s中每个数字的值.
结果.

该算法为O(N).对于列表中的每个数字,我们有一定数量的操作要做,因为我们最多有64位数.对于大b,最后回复最坏的是O(N).我们可以通过计算每个数字的所有i的i ^^(m%b)来在恒定空间中完成这最后一步(同样,我们有一个恒定的数字位数).

例:

n = 3,m = 2. list =[5 11 5 2 11 5 2 11]

首先我们选择一个基数b.显然我们必须选择基数3.

xor表供参考:

  0|1|2
0|0|1|2
1|1|2|0
2|2|0|1

计算:

  5     11      5      2     11      5      2     11
0^0=0. 0^1=1. 1^0=1. 1^0=1. 1^1=2. 2^0=2. 2^0=2. 2^1=0.
0^1=1. 1^0=1. 1^1=2. 2^0=2. 2^0=2. 2^1=0. 0^0=0. 0^0=0.
0^2=2. 2^2=1. 1^2=0. 0^2=2. 2^2=1. 1^2=0. 0^2=2. 2^2=1.

m % b = 2.

因此我们有s ^^ 2 = [001].我们为每个数字i生成一个i ^^ 2表,然后进行反向查找.

   i | 0 | 1 | 2 |
i^^2 | 0 | 2 | 1 |

0 -> 0
0 -> 0
1 -> 2

我们最后将结果转换回二进制/十进制.[002] = 2.