使用哈希映射查找单个整数

Question

一个编码问题：Given an array of integers, every element appears twice except for one. Find that single one.它需要a linear runtime complexity。

我的解决方案：

public class Solution {
    public int singleNumber(int[] A) {
    HashMap<Integer, Integer> lut = new HashMap<Integer, Integer>();
     for (int i=0; i<A.length; i++){
         if(lut.containsKey(A[i])){
             lut.remove(A[i]);
         }
         else{
             lut.put(A[i],1);
         }
     }
     Set<Integer> keys = lut.keySet();
     System.out.println(keys.size());
     for(Integer integer: keys)
         return integer;
     return (Integer) null;
 }

}

我认为复杂性是O(n)，因为它只经过一次数组，而HashMap使用固定的时间来获得一个元素。但在网上判断后，它说我的代码是time limit。有人能指出为什么这会超过时间限制吗？如何改进？

Answer 1

我怀疑设置时间限制时考虑到了特定的实现。对我来说，你的解决方案看起来应该是线性时间，但它可能是一个比这段代码大得多的常数：

public int findSingleNumber(int[] array) {
    int result = 0;
    for (int item : array) {
        result ^= item;
    }
    return result;
}

这使用了这样一个事实，即除了我们想要的项目外，所有项目都会出现两次，所以如果它们被异或在一起，它们会相互抵消。我们只剩下我们要找的号码了。

我想补充一点，像这样的谜题很有趣，也很有启发性，但解决方案很少是你想在实际应用中使用的。