rod*_*art 6 c algorithm discrete-mathematics array-algorithms
你有一个n = 2k + 2个元素的数组,其中2个元素没有配对.8个elemets数组的示例:1 2 3 47 3 1 2 0."47"和"0"没有数组配对.如果我有只有1个元素没有配对的数组,我用XOR解决了这个问题.但我有2个不配对的元素!我能做什么？解决方案可以是O(n)时间性能和O(1)额外存储器.
一些提示......
这将需要2次通过.首先,浏览列表并将所有元素XOR组合在一起.看看你得到了什么.从那里继续.
编辑:关于第一遍结果的关键观察应该是它显示了2个不成对元素不同的位集.
使用 INT_MAX/8 字节内存。走阵。将每个值对应的位与 1 进行异或。如果有 0 或 2 个实例，则该位最终为 0。如果只有 1 个实例，则将其设置。O(1) 内存，O(N) 时间。