线性时间,常数空间算法,用于查找列表中出现1次的元素

Question

给定n个整数的列表,其中列表中的每个整数都存在两次,除了一个元素,它在列表中存在一次.例如,

[1 3 3 6 2 7 1 2 7]

我需要找到一个线性时间O(n)和一个常量空间O(1)算法,它返回列表中存在一次的元素.在上面的示例中,算法应返回6.请注意,列表不是由任何特定顺序提供的.(列表中元素的顺序是随机的).

我可以使用字典在O(n)线性时间内解决这个问题但不幸的是字典需要O(n)空间.有任何想法吗？

Answer 1

解决这个难题需要知道一个小技巧: - XOR一个数字本身甚至次数都会导致零.而且,你可以在XOR其他数字之间产生临时结果; 订单无关紧要.

因此,如果您XOR将数组中的所有值都放在一起,您将只获得阵列中唯一的数字:

int res = 0;
for (int i = 0 ; i != array.size() ; i++) {
    res ^= array[i];
}
cout << res << endl;