200行數字每行200個行內已從大到小排列行與行之間無聯繫如何從4W個數據中取出600個最大數？

01-31

RT 求演算法

每行第一個元素建個最大堆，取了一個元素就把元素所在行的下一個加入堆

經典的k路歸併問題，用堆(優先順序隊列)

你的問題按照我的理解其實是外部排序的後面歸併步驟。

相當於下面的外排序的第四步驟開始：

讀入100 MB的數據至內存中，用某種常規方式（如快速排序、堆排序、歸併排序等方法）在內存中完成排序。

將排序完成的數據寫入磁碟。

重複步驟1和2直到所有的數據都存入了不同的100 MB的塊（臨時文件）中。在這個例子中，有900 MB數據，單個臨時文件大小為100 MB，所以會產生9個臨時文件。

讀入每個臨時文件（順串）的前10 MB（ = 100 MB / (9塊 + 1)）的數據放入內存中的輸入緩衝區，最後的10 MB作為輸出緩衝區。（實踐中，將輸入緩衝適當調小，而適當增大輸出緩衝區能獲得更好的效果。）

執行九路歸併演算法，將結果輸出到輸出緩衝區。一旦輸出緩衝區滿，將緩衝區中的數據寫出至目標文件，清空緩衝區。一旦9個輸入緩衝區中的一個變空，就從這個緩衝區關聯的文件，讀入下一個10M數據，除非這個文件已讀完。這是「外歸併排序」能在主存外完成排序的關鍵步驟 -- 因為「歸併演算法」(merge algorithm)對每一個大塊只是順序地做一輪訪問(進行歸併)，每個大塊不用完全載入主存。

你的題目200行取 600個數，根據你自己的需求來設置不大於600的緩衝。

https://zh.wikipedia.org/wiki/%E5%A4%96%E6%8E%92%E5%BA%8F

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

使用lua語言

1,首先取200行首個數字遍歷,取最大值,記 xMax

2,將所有數據投入變數table, key = xMax - 每個數據的值 + 1, value = 坐標

3,從小到大用for循環取出前600個數

空間複雜度為 O(1),前兩部快,第三部看數值分步

應該歸併吧

如果要求取出的600是有序的，用歸併（堆）。

否則可用600除以200等於3，比較200行每行的第三個數，將最大的那個所在行的前三個數取出，他們一定在前600中。

此時變成取597個數，遞歸此過程。

這種方法選取的結果是無序的。

這個不是歸併排序的最後一步么。。。不過從N+M變到了600長度

隨便想了想：拓展到（N，k）的話（這裡的N=4W，每個row的長度就是根號N， k=600）

1）merge到一個長度為k的array，O(N), 空間常數

2）建一個大小為k的minimum heap， O(N), 新來的數比棧頂大就pop and push，空間常數

3）由quick select的啟發：

對每一行按中位數排序，中位數最小的一行在上面。任取一個中位數，就取那個中位數的中位數吧。它所在的行和列把這個類似matrix的東西劃成4個區域，右下的任何一個數一定比左上和左下的任何一個數大，與右上任何一個數的關係都不能確定。

換而言之，

1）右下這N/4的數一定在前N/2

2）左下任何一個數都不在前N/4

3）左上任何一個數都不再前3N/4

那左邊都不要了。

突然：

T(n) = T(n/2) + (中位數排序） =&> log(N) &< T(N) &< N

///我認為中位數排序是o(N)

//因為，

$left: n^{1/2}log(n^{1/2})quad right: n\ Rightarrow left: n^{1/2}log(n)quad right: n^{1/2}\ Rightarrow let m^{2}=n left: mlog(m^2)quad right: m\ Rightarrow log(m) = o(m)$

大小為4k的時候，隨便怎麼弄吧。隨便想想的，總覺得不太對，請指正。

令N為行數，M為行長度，求前K大

1 大根堆每行第一個數拿出來建大根堆，堆節點同時保存其行號和索引。O(n)

每次取堆頂元素，若不是所在行最後一個，根據索引添加其所在行下一個。每次操作O(logn)

K logN

2 歸併排序

每次歸併只保留前k大的部分

K logN

200行數字每行200個 行內已從大到小排列 行與行之間無聯繫 如何從4W個數據中取出600個最大數？

200行數字每行200個行內已從大到小排列行與行之間無聯繫如何從4W個數據中取出600個最大數？