如何查找数组中不会出现两次的唯一数字
以下是来自面试的内容：
在一个包含整数的给定数组中，除了一个数字外，每个数字都重复一次，不重复。 写一个函数，find不重复的号码。
我想过使用HashSet，但它可能会使一切复杂化…
任何想法的简单解决scheme？
你可以定义一个整数“结果”初始化为0，然后通过对数组中的所有元素应用异或逻辑来执行一些按位操作。
最后，“结果”将等于仅出现一次的唯一元素。
result = 0 for i in array: result ^= i return result http://en.wikipedia.org/wiki/Bitwise_operation#XOR
例如，如果数组包含元素[3,4,5,3,4]，则algorithm将返回
3 ^ 4 ^ 5 ^ 3 ^ 4
但异或运算符^是关联和可交换的，所以结果也将等于：
（3 ^ 3）^（4 ^ 4）^ 5
由于i ^ i = 0，对于任何整数i，而我^ 0 = i，你有
（3 ^ 3）^（4 ^ 4）^ 5 = 0 ^ 0 ^ 5 = 5
我以前见过这个问题。 这是一个骗局。 假设所有重复的数字都出现两次，你可以这样做：
int result = 0; for (int a : arr) result ^= a;
另一个“普通”的解决scheme（Java）：
public static int findSingle(int[] array) { Set<Integer> set = new HashSet<Integer>(); for (int item : array) { if (!set.remove(item)) { set.add(item); } } assert set.size() == 1; return set.iterator().next(); }
在我看来，XOR的解决scheme很漂亮。
这个不像XOR那么快，但是HashSet的使用使它接近于O（n）。 而且它更可读。
已经给出了最好的答案（异或元素），这是提供一个替代的，更一般的方法。
如果input数组将被sorting（我们可以对其进行sorting），那么我们可以简单地迭代成对的元素（步进2），如果“pair”的元素不同，我们就完成了：
public static int findSingle(int[] arr) { Arrays.sort(arr); for (int i = 0, max = arr.length - 1; i < max; i += 2) if (arr[i] != arr[i + 1]) return arr[i]; return arr[arr.length - 1]; // Single element is the last }
注意：这个解决scheme对input数组进行sorting; 如果这是不需要或不允许的，可以先克隆：
arr = arr.clone();
如果input数组是sorting的，则Arrays.sort(arr)调用可以被排除在外。
概括
这种解决scheme的优点是它可以应用于所有可比较的types，因此可以进行sorting（types实现Comparable ），例如String或Date 。 XOR解决scheme仅限于数字。
这是一个稍微修改的版本，它接受任何可比的元素types的input数组：
public static <E extends Comparable<E>> E findSingle(E[] arr) { Arrays.sort(arr); for (int i = 0, max = arr.length - 1; i < max; i += 2) if (arr[i].compareTo(arr[i + 1]) != 0) return arr[i]; return arr[arr.length - 1]; // Single element is the last }
注意：在大多数情况下，您也可以使用arr[i].equals(arr[i + 1])来比较元素，而不是使用Comparable.compareTo() 。 有关详细信息，请阅读链接的javadoc。 引用相关部分：
强烈build议，但不是严格要求
(x.compareTo(y)==0) == (x.equals(y))。 一般来说，任何实现了Comparable接口的类违反了这个条件都应该清楚地说明这个事实。 推荐的语言是“注意：这个类有一个自然的sorting，与平等不一致”。
现在你可以用一个String[]来调用它，例如：
System.out.println(findSingle(new String[] { "1", "2", "3", "1", "3" }));
输出：
2
最后说明：
从问题陈述开始，不检查是否有多于两个元素出现，并且数组长度是否是奇数。 另外第二个例子不检查null值，如果需要的话，这些将被添加。
这是一个稍微模糊的方式来做到这一点：
List list = Arrays.asList(a); int result; for(int i:a) { if(list.indexOf(i)==list.lastIndexOf(i)) { result = i; break; } }
result将包含不重复的值。
