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

共:💬24 🌺10 新:

老大河待整

分页树展主题 · 全看首页上页下页末页

- - - - 复 Implementation using HashSet.
        家园 hash是对的。但是，你的contains()如何最快实现呢！
        复 hash是对的。但是，你的contains()如何最快实现呢！
        家园 There are always two solutions for the classic issue.
        As for contains() implementation, check out Sun's JDK implementation. I believe it's O(1) as the Javadoc declared.
        Well, there are always two solutions for the classic issue. One is the solution you mentioned above, and the other is the one I gave.
        bigbug
      - 复 bigbug可能写得比较简单吧
        家园 不是这样解决的
        还是看我给bigbug的回帖吧。
        直接hash一下是绝对不行的。
        这个问题我记得是在divide and conquer原则下解决的，朝这个方向想才行。
        复不是这样解决的
        家园 先排再找有什么问题吗?
        排序的计算量是O(nlogn)，排好序的数列中找出两个相同的数字的计算量O(n)，总的计算量是O(nlogn)。
        O(nlogn)一般就是最优解了，O(n)不大可能吧？
        不排序直接找，可能也是一个排序的变形算法。比起先排再找也就是少了一个O(n)的计算量。
        复先排再找有什么问题吗?
        家园 仍然不是正解
        不排序直接找，可能也是一个排序的变形算法。比起先排再找也就是少了一个O(n)的计算量。
        你的第一句可能对，第二句就不对了。可能是在排序的过程中找到（我的记忆和这个不同，我自己现在能够想到的也是这样，但这绝对不是正解），但是这个不需要排序。比如，给出一个序列，找到它的median；还有，给出一个序列找到第K个最大的。这两个问题根本不用排序。我的问题和这两个类似，也不需要排序。
        复先排再找有什么问题吗?
        家园 俄也是这么想的
        先排序再算一下两两之间的差，差值为零的不就是么...
        不过如果他需要的是两个相同值的原始位置，而非值本身，就要多费些周章...
        复俄也是这么想的
        家园 我的做法（非正解）
        就是利用quicksort的过程去找，时间上小于等于quicksort的O(nlogn)：
        1、取第一个元素A将序列分成两份，左边部分的都比A小，右边部分的都比A大。A可能就是我要找的，如果是这样，就结束了。否则：
        2、在左边部分重复1；仍然没有找到，
        3、在右边部分重复1；
        复我的做法（非正解）
        家园 Quick Sort的最差情况是平方级别的
        平均情况为O(n log n)
        复我的做法（非正解）
        家园 可是devide and conquer本身就只能应用于已经排序好的数列吧
        老兄的算法排序过程是O(nlogn)，搜索算法（binary search）算法是O(logn)，合计O(nlogn)

分页树展主题 · 全看首页上页下页末页

有趣有益，互惠互利；开阔视野，博采众长。
虚拟的网络，真实的人。天南地北客，相逢皆朋友

版面群落趣味社区帮助常见问题网站简介基本河规隐私条款使用条款广告说明