查找单个号码列表中的 [英] Finding a single number in a list

问题描述

什么是最好的算法查找一个数字，只发生一次，其中具有所有其它数量发生两次确切列表。

What would be the best algorithm for finding a number that occurs only once in a list which has all other numbers occurring exactly twice.

所以，在整数的列表（可以把它作为一个数组），每个整数正好重复了两次，只有一个除外。为了找到一个，什么是最好的算法。

So, in the list of integers (lets take it as an array) each integer repeats exactly twice, except one. To find that one, what is the best algorithm.

推荐答案

最快的（O（n））的，最高效的内存（O（1））的方法是使用XOR运算。

The fastest (O(n)) and most memory efficient (O(1)) way is with the XOR operation.

在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，这是发生一次唯一的一个。

This prints "1", which is the only one that occurs once.

这工作，因为你第一次打了一些它本身标志着NUM变量，第二次就取​​消标记NUM与自身（或多或少）。唯一一个仍然无人盯防的是你不重复的。

This works because the first time you hit a number it marks the num variable with itself, and the second time it unmarks num with itself (more or less). The only one that remains unmarked is your non-duplicate.

这篇关于查找单个号码列表中的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！