问题我是在面试时给出的.我接近解决方案,但不幸的是没有解决它.
假设我们有一个包含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,因为它只发生了两次.