在列表中查找单个数字

找到在列表中只出现一次的数字的最佳算法是什么,其中所有其他数字恰好发生两次.

因此,在整数列表中(让它作为一个数组),每个整数重复两次,除了一个.找到那个,什么是最好的算法.

1> Kyle Cronin..：

---

最快(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(或多或少).唯一没有标记的是您的非重复.

---

负数是位数,就像正数一样.XOR不关心

---

这是"最佳"解决方案,只要您可以实际对项目进行异或即可.意思是,它取决于数据类型.如果项目是字符串,我不确定你是否可以这样做.当然,在这种情况下,它可以通过一层抽象来解决......

2> Tyler..：

---

顺便说一句,您可以扩展这个想法,以便在重复列表中快速找到两个唯一的数字.

我们称之为唯一数字a和b.首先考虑一切的异或,正如凯尔建议的那样.我们得到的是^ b.我们知道a ^ b!= 0,因为a!= b.选择任何1位a ^ b,并将其用作掩码 - 更详细:选择x作为2的幂,使x&(a ^ b)非零.

现在将列表拆分为两个子列表 - 一个子列表包含y和x == 0的所有数字y,其余子列表位于另一个子列表中.顺便说一下,我们选择x,我们知道a和b在不同的桶中.我们也知道每对副本仍然在同一个桶中.因此,我们现在可以独立地将"XOR-em-all"技巧应用于每个桶,并发现a和b完全是什么.

巴姆.

3> csmba..：

---

O(N)时间,O(N)记忆

HT =哈希表

HT.clear()会查看列表,以便查看您看到的每个项目

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

最后,HT中的项目是您要查找的项目.

注意(credit @Jared Updike):此系统将查找所有项目的奇数实例.

---

评论:我不知道人们如何投票给你提供NLogN性能的解决方案.宇宙是哪个"更好"？我更加震惊你标记了NLogN解决方案的接受答案...

我同意,如果要求内存保持不变,那么NLogN将是(到目前为止)最佳解决方案.

---

看一下第一行,粗体:我明确地说它是O(N)时间,O(N)记忆,所以你不要批评我对任何我没有指出的建议.