algorithm - 在列表中查找单个数字

Question

查找列表中仅出现一次的数字(而所有其他数字恰好出现两次)的最佳算法是什么。

因此，在整数列表中(让我们将其视为数组)，每个整数恰好重复两次，除了一次。为了找到那个，最好的算法是什么。

Answer 1

最快 (O(n)) 和内存效率最高 (O(1)) 的方法是 XOR 运算。

在 C 中:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

这会打印“1”，这是唯一出现一次的。

这是有效的，因为第一次输入数字时，它会用自身标记 num 变量，第二次它会用自身取消标记 num (或多或少)。唯一未标记的是您的非重复项。