在列表中查找单个数字

Question

12 浏览2023年5月21日

匿名的 2022年7月14日

0 Comments

这个问题已经有了答案:

如何在列表中找到只出现一次的数字[重复]

找到在其它数字都出现两次的一个列表中仅出现一次的数字，最好的算法是什么。

在整数的列表中（让我们把它看作一个数组），每个整数都恰好重复两次，除了一个。为了找到那个数字，最好的算法是什么。

admin 更改状态以发布 2023年5月21日

0

2 答案

匿名的 · Answer 1 · 2022-07-14T20:57:58+00:00

顺便说一句，您可以扩展这个想法，以在重复项列表中非常快地找到两个唯一的数字。让我们称唯一的数字为 a 和 b。首先，像 Kyle 建议的那样对所有内容进行异或运算。我们得到的是 a^b。我们知道 a^b != 0，因为 a != b。选择 a^b 中的任何 1 位，并将其用作掩码——更详细地说：选择 x 作为 2 的幂，使得 x &(a^b) 是非零值。现在将列表拆分为两个子列表——一个子列表包含 y & x == 0 的所有数字 y，其余数字放在另一个子列表中。通过我们选择的 x 的方式，我们知道 a 和 b 在不同的桶中。我们还知道每一对重复项仍在同一个桶中。因此，我们现在可以将 ye olde \"XOR-em-all\" 技巧分别应用于每个桶，并完全发现 a 和 b 是什么。砰。

匿名的 · Answer 2 · 2022-07-14T20:57:58+00:00

最快（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（大多数情况下）。唯一留下未标记的是您的非重复项。