一个面试题，帮忙分析思路

Question

一个文件中有10万行数据，每行一个人名，有重复数据。现要求将文件中重复次数最多的100个名字和次数筛选出来并降序排列。我第一印象就是循环操作，但这样的做法应该效率很低也想过用数据库来处理，但人家要求是java处理有没有高手帮忙分析一下

Answer 1

我的想法是，首先全部查询出来list，然后放在一个map里面（“人名”，“次数”）然后得得到这个重复的次数

Answer 2

ArrayList 实现 Iterator 接口 便利

Answer 3

用一个双向链表存放人名和出现次数（存在一个node里，一人名对应一个）一个HashMap的key保存出现过的人名，value保存人名的node指向
一个TreeMap的key保存人数，value保存该升序链表中该人数的最右边节点如果没有在HashMap里找到，插入在链表头部如果找到了，就更新该节点（人数+1），然后搜索TreeMap，找到小与或等于自己的最大值，在右边插入后，把自己在TreeMap中更新（假设自己是3，那就是3在该有序链表中的最右边的3），TreeMap里就是保存某个人数在链表中的最右节点。

Answer 4

select name,sum(name) from table group by name order by sum(name) desc;试试

Answer 5

查出来的结果放到ArrayList里面jsp上通过<logic:iterate>显示出来

Answer 6

public class T { public static void init() throws IOException {
File f = new File("d:/ttt.txt");
FileWriter writer = new FileWriter(f);
Random r = new Random();
for (int i = 0; i < 100000; i++) {
writer.write("名字" + r.nextInt(1000) + "\r\n");
}
writer.flush();
} public static void go() throws IOException {
BufferedReader reader = new BufferedReader(new FileReader("d:/ttt.txt"));
Map<String, Integer> map = new HashMap<String, Integer>();
String name = "";
while ((name = reader.readLine()) != null) {
if (map.get(name) == null) {
map.put(name, 1);
} else {
map.put(name, map.get(name) + 1);
}
} Entry[] entrys = (Entry[]) map.entrySet()
.toArray(new Entry[map.size()]);
Arrays.sort(entrys, new Comparator<Entry>() {
@Override
public int compare(Entry e1, Entry e2) {
int a = (Integer) e1.getValue();
int b = (Integer) e2.getValue();
return a < b ? 1 : a > b ? -1 : 0;
}
});
for (int i = 0; i < 100; i++) {
System.out.println(entrys[i].getKey() + " 个数"
+ entrys[i].getValue());
}
} public static void main(String[] args) throws IOException {
init();
go();
}
}

Answer 7

首先Map不能用。 键是不能相同的
用Java  做的话 像这么多数据调用数据库的存储过程性能是比较好的

Answer 8

谁说map不能用
我在9楼写的就是用map
虽然是硬循环 效率不高

Answer 9

人家都说了不能用数据库，要求用java。
关注下。

Answer 10

真白痴的题目，我用JAVA调用select name,sum(name) from table group by name order by sum(name) desc; 呢？

Answer 11

10w的数据量,不算大.1.用Map做,9楼的代码看着可以.2.读到一个数组中，先降序排序（自己写一个Comparator或用Collection.reverseOrder()),再遍历一遍把不同的名字输出到结果。比第一种效率差一些。

Answer 12

select name,sum(name) from table group by name order by sum(name) desc;
文件可以直接转成数据库中的数据？！怎么做到呀？！

Answer 13

首先感谢大家的分析
这是我第一次在小D上发布
效果超出我的预期
总结一条：高手如云，热心如潮其实这是千橡互动的一个面试题
我是在网上看到的从效率方面考虑，估计都不会很好，毕竟这么多数据需要读进内存才能处理9楼的算法蛮巧妙的，用数据结构来避免过多的循环，佩服！SQL文的做法我没有验证，但和我的预想相近，谢谢。