分享
从N个数组中找出出现最多的前K个数？
有N个数组（N范围为1-2000），每个数组里存放的是M个64位的整数（M范围为1-2000），单个数组中数字不重复。求这些数组中出现最多的前K个数（假如K为10）？目前想到的是将这些数放到map中，然后对map结果排序，取出其中最多的几个数。请问有更好的办法吗？很多答案都提到了使用map-reduce，不过由于目前用户量比较小，后期用户量也不会太大，所以考虑把用户关系图直接读入内存进行运算。原始问题：社交网站上，A关注了1-2000个用户，同时这1-2000个用户分别关注了1-2000个用户，如何找出这二度人脉中出现最多的用户，然后给A推荐？
回复 ( 7 )
=======================
补充：
我跟 @陈硕 代码思路的区别在于：
当数组较小、可以直接加载内存时，用 @陈硕 的代码，直接排序即可
但当数组很大、要考虑分布式时，若还是暴力地对二度好友统计排序，复杂度非常高！（哪怕是用Map-Reduce）
所以要换一种巧妙的思路，设计Map-Reduce的<key,value>，使得复杂度降低
=======================
直接回答原始问题：
首先，我们注意一个重要的结论：对于某用户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，设计<key=Ai的某个一度好友，value=Ai剩下的一度好友>，比如A1有A，B，C，D四个一度好友，则有四个<key,value>对儿，即<A,{B,C,D}>,<B,{A,C,D}>,<C,{A,B,D}>,<D,{A,B,C}>
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
unordered_map<int64_t, int> count;
for all id:
count[id]++;
vector<pair<int, int64_t> > freq;
for item in count:
freq.emplace_back(item.second, item.first);
partial_sort(freq, 10); // or nth_element()
学学课程stream mining：
这放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。