使用散列图查找单个整数

编码问题：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。有人能指出为什么这超过了时间限制吗？如何提高？

来源

2015-03-02 byteBiter

您的代码具有线性时间复杂度。 – Eran 2015-03-02 06:53:21

鉴于你只关心密钥集，我个人使用'HashSet '代码清晰。但是，是的，假设没有散列桶冲突，这应该具有线性复杂性。话虽如此，有一个简单的解决方案，使用很少的空间。 – 2015-03-02 06:55:29

我怀疑已经设定了一个具体的实施时间限制。您的解决方案看起来应该是线性的时候我 - 但它可能比这个代码显著更大的常数因子：

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

它使用的事实，除非我们想要出现一个所有项目准确的两倍，因此，如果他们将它们异或，他们会相互抵消。我们只剩下我们正在寻找的号码。

我会补充说，这样的谜题很有趣，并且可以让人大开眼界 - 但是解决方案很难你想在实际应用中使用。

来源

2015-03-02 06:58:21

嗨，当然这是最好的解决方案。我只是好奇为什么'leetcode'网站不能接受我的答案... – byteBiter 2015-03-02 14:42:58

@Liquid：呃，我建议他们可能有一个非常小的超时...一个需要的解决方案不只是O（ n），但也有一个小常数因子。 – 2015-03-02 14:45:18

使用散列图查找单个整数

回答

相关问题