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

Question

以下内容来自求职面试:

在包含整数的给定数组中,除了一个数字之外,每个数字重复一次,不重复.编写一个函数,查找不重复的数字.

我想过使用HashSet,但它可能会使一切变得复杂......

任何简单解决方案的想法？

Answer 1

您可以定义一个初始化为0的整数"result",然后通过将XOR逻辑应用于数组中的所有元素来执行一些按位操作.

最后,"结果"将等于仅出现一次的唯一元素.

result = 0
for i in array:
  result ^= i
return result

http://en.wikipedia.org/wiki/Bitwise_operation#XOR

例如,如果您的数组包含元素[3,4,5,3,4],则算法将返回

3 ^ 4 ^ 5 ^ 3 ^ 4

但是XOR运算符^是关联的和可交换的,因此结果也将等于:

(3 ^ 3)^(4 ^ 4)^ 5

因为对于任何整数i,i ^ i = 0,并且i ^ 0 = i,所以你有

(3 ^ 3)^(4 ^ 4)^ 5 = 0 ^ 0 ^ 5 = 5

Answer 2

我以前见过这个问题.这是一个技巧.假设所有重复的数字恰好出现两次,你可以这样做:

int result = 0;
for (int a : arr)
    result ^= a;

Answer 3

另一个"普通"解决方案(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的解决方案很漂亮.

这个没有XOR快,但使用HashSet使其接近O(n).它肯定更具可读性.

Answer 4

已经给出了最好的答案(对元素进行异或),这是为了提供一种替代的,更通用的方法.

如果输入数组将被排序(我们可以对其进行排序),我们可以简单地迭代遍历元素(步进2),如果"对"的元素不同,我们就完成了:

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
}

注意:此解决方案对输入数组进行排序; 如果这是不需要的或不允许的话,可以先克隆它:

arr = arr.clone();

如果输入数组已排序,则Arrays.sort(arr)可以不使用该调用.

概括

该解决方案的优点在于它可以应用于所有可比较的类型,因此可以进行分类(实现的类型Comparable),例如String或Date.该XOR解决方案仅限于数字.

这是一个稍微修改过的版本,它采用任何可比较的元素类型的输入数组:

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.引用相关部分:

强烈建议,但并非严格要求(x.compareTo(y)==0) == (x.equals(y)).一般来说,任何实现Comparable接口并违反此条件的类都应该清楚地表明这一事实.推荐的语言是"注意:此类具有与equals不一致的自然顺序."

现在你可以用一个String[]例子来调用它:

System.out.println(findSingle(new String[] { "1", "2", "3", "1", "3" }));

输出:

2

最后的说明:

从问题陈述开始,不检查元素的出现次数是否超过2次,也不检查数组长度是否为奇数.此外,第二个示例不检查null值,必要时将添加这些值.