关于java一道面试题

Question

如果有10万字符串数组，如何快速的算出重复出现最高的字符串。

Answer 1

1.基本设计：首先定义两个数组，一个数组存放十万个字符串。另外二维数组用于遍历的时候，当有新的字符串的时候就添加进去，以及存放出现的次数。（也可以用集合，利用集合key,value的一些性质更快）

Map<String,Integer> map = new HashMap<>();
String[] string = {"abc","123","234","345","234","234","234","345","345","345","345","234","234"};
for(String s:string){
    Integer count = map.get(s);
    map.put(s,count==null?1:count+1);
}
int max = 0;
for(Map.Entry<String,Integer> entry:map.entrySet()){
    if(entry.getValue()>max){
        max = entry.getValue();
    }
    System.out.println("key:"+entry.getKey()+",value:"+entry.getValue());
}
System.out.println(max);

2.第一点优化，当一个字符串出现次数大于一半时，可以结束循环。

第二点优化，当前出现的最多的字符串的次数与第二多字符串次数的插值大于剩余字符串的时候，可以结束循环。

第三点优化（有可能是负优化），遍历的时候，每查询一个字符串有两种情况：没出出现过（加入数组），已经出现过（对应的字符串次数+1，这时候可以考虑增加后与其前一个字符串比较出现次数，如果大于则交换位置，并且再次与前一个比较。这一点在极端的情况下，如果十万个字符串都是没有出现过的，则是负优化。这个优化的理由是因为，当你遍历二位数组的时候，从头往前遍历，理论上应当认为出现次数越多的字符串更容易再次出现。）