主题：求教大家一个算法问题 -- looklook
家园 求教大家一个算法问题 这个题以前上学的时候做过的，昨天忽然被问到，一下子给不出最优解。回家想了想，觉得自己想到的好像不是当年老师在黑板上写的最优解（老师当年在黑板前写的情形历历在目，就是想不起写的是啥
）。请大家帮忙看看，多谢多谢！题：一个序列中只有两个数相同，如何用最快的方法找到这两个数？
家园 我在另外一个地方问 有人告诉我，不计存储空间，以这个序列的最大值N建一个数组，然后将序列中的每个数作数组下标写进数组，写两次的就是。这是一种hash方法。
家园 这就相当于SQL中最常用的方法啊，select *,count(*) as N having N=2; 家园 這不是pigeon hole sorting的算法嗎:) 家园 这是个经典题目， 答案的确如此。原题是这样的： 有一百个数， 比0大， 比100小。 其中有两个是相同的。
如果数字无限制， 还是用这个办法。 只不过先把数字都HASH到0到100。
家园 Variation of the classic issue. There are lots of variation of the classic issue.
One variation is: there is a character sequence composed of 26 English alphabets: a-z, assuming all lower case. How to find the duplicate character in the sequence if there is any?
The solution is to use an array of 26 to hold a-z. If there is an array element being written twice, then that\'s the duplicate.
As a matter of fact, this is one of the questions in a Microsoft interview.
bigbug
家园 not the most efficient method you sure this is the solution for msft interview question?
if the sequence is continuous (but one missing/duplicating) and bounded, the solution is to take the summation and then get the one missing/duplicating by comparing with the summation of the whole continuous sequence. (actually, i guess one more function, e.g. summation of squres is needed to find the duplicating/missing couple).
家园 Yes, it's the solution for Microsoft interview question. Yes, I am sure it's the solution for Microsoft interview question because I had it before and confirmed with the interviewer.
家园 这恐怕不能称为是一种hash方法 A hash function (or hash algorithm) is a way of creating a small digital "fingerprint" from "any kind of data".
我同意楼主的意见, 这个问题的正解是不用hash.即使是子衿提到的非整数情况, 也应该不需要用到hash--只要是数字, 还是容易比较的.
如果这个问题继续扩展呢? 找出一个string array中两个相同的; 找出一个object array中两个相同的, 这恐怕就非用hash不可了?
当然, 在实际工作中, 楼下的大虫兄的方法会是我最先想到的.
家园 这个我也想过的，但是这个方法只限于整数 如果是浮点数则不适应，但是可以用更一般的hash方法，可用什么函数会有比较高的性能，也还是要取决于数据的分布。
家园 的确，浮点数的情况比较麻烦，可能还是先排序快... 要建一个万能hash table也要费不少代价。
家园 Use Hashset. Use Hashset.
bigbug
家园 这是个algorithm问题，不能这样解决 所谓算法，就是让你给出一种算法（说明是怎么解决这个问题的），一般涉及时间和空间效率。这个题要求的是时间上的效率。
退一步，排序之后再找是一种方法，但不是最优的方法。因为这个问题本身不需要排序，先排再找是画蛇添足。
hashset是个暗箱，它用的只能是一种较好的排序算法，有很大的适用性，但是针对具体问题，就不行了。而且，这不是解决算法问题的方法。
家园 bigbug可能写得比较简单吧 就是用一个hash表和函数， 把这个序列hash到表中，如果有多个collision，
再对collision的部分用其他的hash函数， 或者再比较
如果选择的hash 函数比较好，可能根本不需要排序
对这个问题，这个方法应该是时间性能比较好的解决方法
家园 Implementation using HashSet. Yes, I put it too simply.
Here is how you can do it:
boolean hasDuplicate(int[] a) {
HashSet hs = new HashSet();
for (int i = 0; i < a.length; ++i) {
if (hs.contains(a[i]) {
return true;
}
else {
hs.add(a[i]);
}
}
return false;
}
Here is some Javadoc for HashSet class:
This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.
So, as you can see, the algorithm takes O(n) time. There is no need for sorting according to the problem requirement.
Of course, you can also define the method to return the actual duplicate number if you want.