最优算法
有N个整数数组成的数组a[N],N个数中只有两个是相同的,且数组中的元素分布无规律,请以最优的算法,找出这个重复的数字。
[解决办法]
先排序再遍历?
[解决办法]
可以试试排序方法,因为其实排序中就涉及到两者比较,一旦找到,就终止排序即可了
选择快速点的排序可能会快点
[解决办法]
不知道你这整数都是什么样的数据,要是没有负数而且数都不会太大的话不妨考虑下建大数组来个空间换时间
[解决办法]
可以建个hash表
[解决办法]
根据实际需要,可以先排序再遍历(耗时间),也可以用hash(耗空间)
[解决办法]
hash,查找是O(1),是凡查找重复的问题都用它。插入时间是T(n),耗费空间是C(n)
[解决办法]
用hash的话, worst case 随时要O(n^2)
[解决办法]
感觉hash和排序都太笨了,需要处理的是两个数,却把其他不相关的也弄进来了。如果这个数N很大的话,太费劲了。
[解决办法]
最近看了个随机算法,我的想法是随机取一个数,然后直接比较,找到了就成功了。找不到就把这个数扔掉,继续随机找。当然这个随机取也采取一定的策略。
[解决办法]
10L,你这个办法在N很大的时候要随机找到那一个重复的数就是平方级的
[解决办法]
我也想用hash表
[解决办法]
弱弱地只能想到set容器,依次插入每个数,插入前查找这个数是否已经在该容器内,每次插入和查找都是logn的复杂度,不过N很大的时候,set可能就爆了。
[解决办法]
排序或者hash,看你希望优化时间还是优化空间了
[解决办法]
果真有O(N)的解法吗,如果不用 hash 的话?
[解决办法]
hash,打点,
平均搜索个数是n/2,最坏是n
[解决办法]
以前讨论过。
建Hash表,遇到冲突就是重复的元素。
最坏的情况也就 O(n).
[解决办法]
是谁跟你说HASH遇到冲突就是重复的?