一种线性时间常数 space 算法，用于查找列表中出现 1 次的元素
A linear time, constant space algorithm for finding an element with 1 occurrence in a list
给定一个包含 n 个整数的列表，其中列表中的每个整数都存在两次，除了一个元素在列表中存在一次。例如，
[1 3 3 6 2 7 1 2 7]
我需要找到一个线性时间 O(n) 和一个常量 space O(1) 算法，该算法 return 是列表中存在一次的元素。在上面的例子中，算法应该 return 6。
请注意，该列表不是由任何特定命令提供的。 （列表中元素的顺序是随机的）。
我可以使用字典在 O(n) 线性时间内解决这个问题，但不幸的是字典需要 O(n) space。有什么想法吗？
解决这个谜题需要知道一个小技巧：XOR-将一个数字与它自身进行偶数次运算得到零。此外，您可以 XOR 其他数字，中间有一个临时结果；顺序无关紧要。
因此，如果您 XOR 将数组中的所有值放在一起，您将获得数组中仅出现一次的唯一数字：
int res = 0;
for (int i = 0 ; i != array.size() ; i++) {
res ^= array[i];
}
cout << res << endl;
您可以将列表中的所有数字异或在一起。结果将是未重复的元素。
给定一个包含 n 个整数的列表，其中列表中的每个整数都存在两次，除了一个元素在列表中存在一次。例如，
[1 3 3 6 2 7 1 2 7]
我需要找到一个线性时间 O(n) 和一个常量 space O(1) 算法，该算法 return 是列表中存在一次的元素。在上面的例子中，算法应该 return 6。 请注意，该列表不是由任何特定命令提供的。 （列表中元素的顺序是随机的）。
我可以使用字典在 O(n) 线性时间内解决这个问题，但不幸的是字典需要 O(n) space。有什么想法吗？
解决这个谜题需要知道一个小技巧：XOR-将一个数字与它自身进行偶数次运算得到零。此外，您可以 XOR 其他数字，中间有一个临时结果；顺序无关紧要。
因此，如果您 XOR 将数组中的所有值放在一起，您将获得数组中仅出现一次的唯一数字：
int res = 0;
for (int i = 0 ; i != array.size() ; i++) {
res ^= array[i];
}
cout << res << endl;
您可以将列表中的所有数字异或在一起。结果将是未重复的元素。