如何查找数组中不会出现两次的唯一数字

以下是来自面试的内容:

在一个包含整数的给定数组中,除了一个数字外,每个数字都重复一次,不重复。 写一个函数,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 ),例如StringDateXOR解决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将包含不重复的值。