主题：求教大家一个算法问题 -- looklook

这个题以前上学的时候做过的，昨天忽然被问到，一下子给不出最优解。回家想了想，觉得自己想到的好像不是当年老师在黑板上写的最优解（老师当年在黑板前写的情形历历在目，就是想不起写的是啥）。请大家帮忙看看，多谢多谢！

题：一个序列中只有两个数相同，如何用最快的方法找到这两个数？

Use Hashset.

bigbug

所谓算法，就是让你给出一种算法（说明是怎么解决这个问题的），一般涉及时间和空间效率。这个题要求的是时间上的效率。

退一步，排序之后再找是一种方法，但不是最优的方法。因为这个问题本身不需要排序，先排再找是画蛇添足。

hashset是个暗箱，它用的只能是一种较好的排序算法，有很大的适用性，但是针对具体问题，就不行了。而且，这不是解决算法问题的方法。

就是用一个hash表和函数， 把这个序列hash到表中，如果有多个collision，

再对collision的部分用其他的hash函数， 或者再比较

如果选择的hash 函数比较好，可能根本不需要排序

对这个问题，这个方法应该是时间性能比较好的解决方法

还是看我给bigbug的回帖吧。

直接hash一下是绝对不行的。

这个问题我记得是在divide and conquer原则下解决的，朝这个方向想才行。

排序的计算量是O(nlogn)，排好序的数列中找出两个相同的数字的计算量O(n)，总的计算量是O(nlogn)。

O(nlogn)一般就是最优解了，O(n)不大可能吧？

不排序直接找，可能也是一个排序的变形算法。比起先排再找也就是少了一个O(n)的计算量。

先排序再算一下两两之间的差，差值为零的不就是么...

不过如果他需要的是两个相同值的原始位置，而非值本身，就要多费些周章...

你的第一句可能对，第二句就不对了。可能是在排序的过程中找到（我的记忆和这个不同，我自己现在能够想到的也是这样，但这绝对不是正解），但是这个不需要排序。比如，给出一个序列，找到它的median；还有，给出一个序列找到第K个最大的。这两个问题根本不用排序。我的问题和这两个类似，也不需要排序。

就是利用quicksort的过程去找，时间上小于等于quicksort的O(nlogn)：

1、取第一个元素A将序列分成两份，左边部分的都比A小，右边部分的都比A大。A可能就是我要找的，如果是这样，就结束了。否则：

2、在左边部分重复1；仍然没有找到，

3、在右边部分重复1；

老兄的算法排序过程是O(nlogn)，搜索算法（binary search）算法是O(logn)，合计O(nlogn)

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.

有人告诉我，不计存储空间，以这个序列的最大值N建一个数组，然后将序列中的每个数作数组下标写进数组，写两次的就是。这是一种hash方法。

如果是浮点数则不适应，但是可以用更一般的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不可了?

当然, 在实际工作中, 楼下的大虫兄的方法会是我最先想到的.

有一百个数， 比0大， 比100小。 其中有两个是相同的。

如果数字无限制， 还是用这个办法。 只不过先把数字都HASH到0到100。