從N個數組中找出出現最多的前K個數？

01-05

有N個數組（N範圍為1-2000），每個數組裡存放的是M個64位的整數（M範圍為1-2000），單個數組中數字不重複。求這些數組中出現最多的前K個數（假如K為10）？
目前想到的是將這些數放到map中，然後對map結果排序，取出其中最多的幾個數。請問有更好的辦法嗎？
很多答案都提到了使用map-reduce，不過由於目前用戶量比較小，後期用戶量也不會太大，所以考慮把用戶關係圖直接讀入內存進行運算。
原始問題：社交網站上，A關注了1-2000個用戶，同時這1-2000個用戶分別關注了1-2000個用戶，如何找出這二度人脈中出現最多的用戶，然後給A推薦？

unordered_map& count;

for all id:

count[id]++;

vector&

&> freq;

for item in count:

freq.emplace_back(item.second, item.first);

partial_sort(freq, 10); // or nth_element()

=======================

補充：

我跟 @陳碩代碼思路的區別在於：

當數組較小、可以直接載入內存時，用 @陳碩的代碼，直接排序即可

但當數組很大、要考慮分散式時，若還是暴力地對二度好友統計排序，複雜度非常高！（哪怕是用Map-Reduce）

所以要換一種巧妙的思路，設計Map-Reduce的&，使得複雜度降低

=======================

直接回答原始問題：

社交網站上，A關注了1-2000個用戶，同時這1-2000個用戶分別關注了1-2000個用戶，如何找出這二度人脈中出現最多的用戶，然後給A推薦

首先，我們注意一個重要的結論：對於某用戶U來說，其所有一度好友之間互為二度好友（因為都經過了U這個點），當然，如果這些二度好友間，存在直接聯繫，那就是一度好友，推薦時，把她們過濾掉就是（補充：多謝 @Jeff Yang 提醒，此結論僅對「關注」是雙向時成立，即A關注B $Leftrightarrow$ B關注A）

基於上面這個重要的點，我們來設計Map-Reduce（假設A有A1, A2,...Ai,...An這n個一度好友）：

1. 輸入：A的這n個一度好友的一度好友list，也就是A1的一度好友, A2的一度好友...An的一度好友

2. Map階段：對於Ai，設計&，比如A1有A，B，C，D四個一度好友，則有四個&對兒，即&,&,&,&

3. Reduce階段：將相同key的value作不去重的合併

4. 輸出：key是某個用戶，value是其可能包含一度好友的二度好友集合，我們找出key=A的那個記錄所對應的的集合，根據A的一度好友列表，過濾掉集合中A的一度好友，將剩下的結果count，取topK推薦給A

複雜度分析：

map階段，map的輸出結果大小=A的所有一度好友的一度好友總和，線性複雜度

reduce階段，簡單的合併操作

count階段，即計算數組中重複次數最多的前K個值，可以先用hash_map等統計用戶ID及其次數，將結果用字典保存，再用堆排序方法，通過維護小頂堆的方式，找出次數最大的前K個ID

學學課程stream mining：

http://www.win.tue.nl/~lamthuy/MyPub/sigkdd2010.pdf

這放noip不就普及組的題么

隨意hash一下想怎麼排怎麼排

穆文的答案假定了關注關係是雙向的，也就是圖是無向圖，但是像微博之類的社交網站，關注關係組成的圖是一個有向圖，這時穆文的答案失效。

另外需要考慮的是，如果考慮關注關係的更新，那麼，map-reduce不太容易做到實時。

所以可以考慮用redis+實時計算的方式

redis的key為所有的uid，value是該uid的關注uid，

查詢時可以採用mget，拿到結果集，再採用陳碩演算法求頻次top-k即可

對於加關注和取消關注，如，A取消關注B或者A關注B，則更新redis中key為A的uid的value集合即可。

從寫程序角度，我想可以用桶排序，既然告訴啦數的範圍為1到2000，那麼可以建立2001個桶，即定義一個64位數組_int64 buket[2001],然後將這N*M個數掃描一遍，buket[i]記錄數字i出現的次數。掃描時間複雜度為O(NM),接下來是求出buket數組中前k大的數，這些數對應的下標就是所求的前K大的數。求前K大的數可以使用最大堆，建堆O(n),於是用時為O(nK)其中n=2000為buket數組大小。總用時O(n*m+2000k),空間複雜度O(n)。本人大二學生一枚，只是發表下個人看法，可能有分析錯誤之處，不知道是不是你想要的的那個意思。

這個問題有點熟悉。

沒錯，就是《Hadoop實戰》的詞頻統計，跟著來一遍，簡單粗暴。

當然，這個是統計所有的頻率，如果只要求top-K，

可以利用將其分割為若干個集合，

對於每個集合用一個大小為k的min heap取top-k頻率的數

然後將這若干個top數，再取個top-k。