作者:每天洗脸的小媳妇_853 | 来源:互联网 | 2023-05-19 19:22
编码问题: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 lut = new HashMap();
for (int i=0; i keys = lut.keySet();
System.out.println(keys.size());
for(Integer integer: keys)
return integer;
return (Integer) null;
}
}
我认为复杂性是O(n)
因为它只通过数组一次并HashMap
使用固定时间来获取元素.但在网上判断之后,就说出了我的代码time limit
.有人可以指出为什么这超过了时间限制?如何提高?
1> Jon Skeet..:
我怀疑时间限制是在考虑具体实施的情况下设定的.你的解决方案对我来说应该是线性时间 - 但它可能是一个比这段代码大得多的常数因子:
public int findSingleNumber(int[] array) {
int result = 0;
for (int item : array) {
result ^= item;
}
return result;
}
这使用了除了我们想要的项目之外的所有项目恰好两次出现的事实,因此如果它们被拼凑在一起,它们将相互抵消.我们只剩下我们正在寻找的号码.
我想补充一点,像这样的谜题很有趣并且可以扩展思维 - 但是解决方案很少是你想要在实际应用中使用的解决方案.