在列表中查找单个数字

2018-06-25 06:49:04

这个问题在这里已经有了答案：

如何找到数组中不会出现两次的唯一数字[重复] 5个答案

最快（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("%in", num);

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

这是有效的，因为你第一次碰到一个数字时，它将自己标记为num变量，而第二次它将自己的数字取消标记（或多或少）。唯一没有标记的是你的不重复。

顺便说一下，您可以扩展这个想法，以便在重复列表中快速找到两个唯一的号码。

我们称之为独特的数字a和b。首先采取一切的异或，如凯尔建议。我们得到的是a ^ b。我们知道a ^ b！= 0，因为！= b。选择a ^ b的任何1位，并将其用作掩码 - 更详细地说：选择x作为2的幂，以使x＆（a ^ b）非零。

现在将列表分成两个子列表 - 一个子列表包含y和x == 0的所有数字y，剩下的列在另一个子列表中。顺便说一句，我们选择x，我们知道a和b在不同的桶中。我们也知道每个重复对都在同一个桶中。所以我们现在可以独立使用各种“XOR-em-all”技巧到每个桶，并且发现a和b是完全的。

巴姆。

O（N）时间，O（N）内存

HT =哈希表

HT.clear（）遍历列表中的每个项目

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

最后，HT中的物品就是你正在寻找的物品。

注意（credit @Jared Updike）：该系统将查找所有Odd项目的实例。

评论：我看不出人们如何投票给出NlogN性能的解决方案。哪个宇宙是“更好”？我更加震惊的是你标记了接受的答案是NLogN解决方案...

但我同意，如果要求内存不变，那么NLogN将是（迄今为止）最好的解决方案。

链接地址: http://www.djcxy.com/p/70787.html