Criss_TieZhu 2021-01-22 14:55 采纳率: 50%
浏览 10
已采纳

关于java一道面试题

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

  • 写回答

1条回答 默认 最新

  • qq_1113502097 2021-01-22 15:22
    关注

    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,这时候可以考虑增加后与其前一个字符串比较出现次数,如果大于则交换位置,并且再次与前一个比较。这一点在极端的情况下,如果十万个字符串都是没有出现过的,则是负优化。这个优化的理由是因为,当你遍历二位数组的时候,从头往前遍历,理论上应当认为出现次数越多的字符串更容易再次出现。)

     

     

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 利用Java语言结合数据库实现-个信息管理系统(如学生管理系统、图书管理系统(可以加上借书还书等功能等)或者小游戏
  • ¥15 Python题,回答一下下啦
  • ¥15 会会信号与系统和python的来
  • ¥15 关于#python#的问题
  • ¥20 oracle RAC 怎么配置啊,配置
  • ¥15 excel 日常使用中出现问题
  • ¥20 pdusession建立失败
  • ¥15 为什么mqtt接收不到数据?
  • ¥15 思科校园网的组建,sos!
  • ¥15 主要进行描述非满管状态下,管路的摩阻系数是怎么变化的,在管路长度方向上是怎么分布的(标签-matlab)