这是我在面试中遇到的问题。我离解决它很近了，但不幸的是没有解决它。
假设我们有一个包含long类型的N个数字的序列，并且我们确定在这个序列中每个数字确实恰好出现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，因为它只出现了两次。
对于每个位，您都要做64个求和运算。对于每个求和，您需要计算sum mod n，这个计算针对每个位返回一个m值，该位应该设置在结果中，并且对于应该不被设置的每个位，返回0。
示例：
n = 3，m = 2。列表为[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位整数求和4个4位整数）
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 位整数不会溢出。
我们可以将异或方法推广到任意的m和n中。我们首先需要选择一个基数b，使得gcd(n, b) = b，且gcd(m, b) < b。由于奇数的n/偶数的m对在基数为2时满足此条件，因此标准二进制异或适用于这些对。
首先，我们定义(a^^n)表示有n个a进行基数为b的一般异或（generalised xor），例如，在标准二进制异或下，a^^2 = 0。
我们需要定义我们的一般异或。我们所需的属性基本上与加法相同（交换律，结合律），并且我们需要a^^b = 0。显然的解决方案是对于基数为b的每个数字，(x^y) = (x+y)%b（让自己相信这个解决方案，它与基数为2的二进制异或相同）。然后，我们将其应用于序列中的所有数字，并最终得到result = s^^(m%b)，其中s是特殊数字。
最后，我们需要将'异或'基数为b的数字恢复到预期的数字。我们可以简单地计算每个数字的i^^(m%b)，i=0..b-1，然后查找在s中每个数字在result中的哪个值。
此算法为O(N)。对于列表中的每个数字，我们要执行一定数量的操作，因为我们最多有64个数字。对于大的b，最坏情况下的恢复操作为O(N)。我们可以通过计算每个数字的i^^(m%b)来在常量空间内完成此最后一步，对于每个数字都要这样做（同样，我们有一定数量的数字）。
n = 3，m = 2。列表 = [5 11 5 2 11 5 2 11]
首先，我们选择一个基数b。显然，我们必须选择基数3。
参考异或表：
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.
i | 0 | 1 | 2 |
i^^2 | 0 | 2 | 1 |
0 -> 0
0 -> 0
1 -> 2
64log（2）/ log（b）个数字，因此我们具有O（1）个数字。每个数字上的操作都是O（1），因此我们总共具有O（1）。 - Nabbint divider = 0;
for (int i = 63; i >= 0; i--) {
divider |= 1 << i;
int a = countAbove(divider);
int b = countBelow(divider);
if (a % n == 0 && b % n == 0) return divider;
else if (a % n == 0) divider ^= 1 << i;
}
如果你在0到(N/n)+1的整数集上有一个一对一的哈希映射，那么你可以通过N次迭代+N/n次迭代解决它，并使用N个内存。然而，这里没有一个一对一的映射。
如果没有内存限制，只需要是常数，你可以定义一个大小为longs域的数组，然后你可以在恒定巨大的内存使用下以2N解决问题。对于每个N中的x，你只需添加到BIGARRY[x]，然后循环遍历BIGARRY寻找m。这很糟糕且无法实现，但符合要求，而且大多数面试题都是思想实验。
by dividing the sequence into 2 sub-seqs
(calculate the size of sub-seqs during the procedure)
while (sizeof(sub-seq) mod n != 0)
do the same porcess on this sub-seq(dividing)
像查找第k个顺序统计量这样的O(N)操作。
我认为你不能仅使用O(1)的额外空间来完成它。
以下是我的理由：你被给定：
由于x_i值中存在重复项，让我们将U定义为唯一值的集合。U中的所有元素都出现了n次，其中一个元素在x_i序列中出现了m次。让我们将较少出现的元素标记为u_0，并将U - { u_0 }标记为U_1。
设S为所有x_i的总和。S可以写成：
sum(x_i) = n * sum(U_1) + m * u_0 = n * sum(U) + (m - n) * u_0