求两个数组的差集
最近看了看各位前辈的面试经验，对一些问题找了一下答案，但是还有很多没有好的思路，求各位帮忙解答。
（1）经典的n个数求前k大的数。分两种情况，第一是没有相同的数，另外一种是有。（有相同的数会有什么影响？怎么优化）
（2）两个文件A和B，求A中没有但B中有的单词。（腾讯和百度面试题，只能n*m时间复杂度么？）
（3）1G的内存可以装入2G的程序么？怎么装？
（4）10亿条短信，找出前一万条重复率高的
2017-07-27 16:30 已编辑 北京邮电大学 Java
关注
全部评论
疯兔子
上海交通大学 C++
1.堆排 2.【小文件】对A中单词建立set（unordered_set更好），然后对B中单词遍历，查set中有没有，复杂度是O(nlogn + mlogn)，unordered_set应该是O（n+m） 【大文件，内存中放不下】对A中单词做hash，然后根据hash值分桶存储在不同文件中；对B中单词做hash，同样根据hash值分桶存储在不同文件中。然后读取按相同值段的A，B文件，按小文件方法处理。 3.关键字：swap 4.对每条短信做hash，然后按hash值分桶存储在不同文件中；逐个遍历文件，统计相同短信出现的频率，同时在内存中建堆，存频率最高的k个。
菜鸟四号
成都东软学院 Java
第三个可以用位运算吧，用一个bit来存一个数
Thare
淘天集团_技术专家
说说我的思路： 1.有相同和没相同应该没什么区别，用堆排。 2.可以考虑先排序然后同时遍历。 3.分页，虚拟内存。 4.可以用Hashmap，key可以用短信的hashcode或者md5值，这样就可以把所有短信的摘要信息一次读入内存，然后遍历。
大树张
大连海事大学 Java
短信那个用map
菜鸟四号
成都东软学院 Java
第四个用树状数组吧
相关推荐
09-22 17:57
华东理工大学 Java 
点赞 评论 收藏
分享