在列表中查找单个数字 [英] 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
", 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屋！