搜尋

首頁  >  問答  >  主體

java - 有一个算法问题想请教,给定一亿个数,如何用最快的方法取出其中最大的三个数。

最近有一个java大神,是蚂蚁支付宝的哦,问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多,在开两百个thread进行排序,取最大,然后对这两百个数进行排序,取前三。其实我的思路根本就没有涉及到算法层面,也只是暴力破解。其实这不是最好的做法,因为这样会严重的浪费资源,然后他的回答是堆排序。我的问题是堆排序是怎样实现的,最好用代码体现出来。

迷茫迷茫2779 天前964

全部回覆(8)我來回復

  • PHPz

    PHPz2017-04-18 09:15:57

    取前三為什麼要排序?新開闢三個變數的空間保存中間結果就行了。

    這種方法的複雜度是O(nk),n是数据总量,k是要获取的数据数量。排序无论是堆排还是快排都是O(nlogn)。当k小于log(2, 10 ** 8)時還是有優勢的,太大了就退化成插入排序了。

    回覆
    0
  • 阿神

    阿神2017-04-18 09:15:57

    有N(N>>10000)個整數,求其中的前K個最大的數。 (稱作Top k演算法問題)。由於(1)輸入的大量資料;(2)只要前K個,對整個輸入資料的保存和排序是相當的不可取的。可以利用資料結構的最小堆來處理此問題。

    最小堆,對於每個非葉子節點的數值,一定不大於孩子節點的數值。這樣可用含有K個節點的最小堆來保存K個目前的最大值(當然根節點是其中的最小數值)。每次有資料輸入的時候可以先與根節點比較。若不大於根節點,則捨棄;否則用新數值取代根節點數值。並進行最小堆的調整。

    由於僅僅保存了K個數據,有調整最小堆的時間複雜度為O(logK),因此TOp K演算法(問題)時間複雜度為O(nlogK).

    回覆
    0
  • PHP中文网

    PHP中文网2017-04-18 09:15:57

    隨手一搜尋
    http://www.cnblogs.com/skywang12345/p/3610187.html

    證明及推導參見演算法導論

    但是可以不用堆吧,畢竟只找3個數字…

    回覆
    0
  • 黄舟

    黄舟2017-04-18 09:15:57

    這不是典型的Top k問題嗎,你可以百度一下Top K

    回覆
    0
  • 大家讲道理

    大家讲道理2017-04-18 09:15:57

    topn的如果說穩妥的答案堆排是沒有錯的 問題是這個3取的。 。 。這麼小的數

    回覆
    0
  • 黄舟

    黄舟2017-04-18 09:15:57

    就是堆排序a

    回覆
    0
  • 天蓬老师

    天蓬老师2017-04-18 09:15:57

    topk求解

    回覆
    0
  • 黄舟

    黄舟2017-04-18 09:15:57

    如果想要最快,我覺得點陣圖排序是我見過的最快的了。

    回覆
    0
  • 取消回覆