第2章数字之魅——寻找发帖“水王”-白红宇

第2章数字之魅——寻找发帖“水王”

阅读量：4678 次

发布时间：2019-06-09

本文共 3027 字，大约阅读时间需要 10 分钟。

寻找发帖“水王”

问题描述

　　Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大"水王"，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该"水王"发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？

解法

采用Map存储每个ID和它出现的次数，之后遍历一遍Map找出其中的“水王”，时间复杂度为O(N)（N为ID贴的总数），代码如下：

1 package chapter2shuzizhimei.findshuiwang; 2  3 import java.util.HashMap; 4 import java.util.Iterator; 5 import java.util.Map; 6  7 /** 8  * 寻找发帖"水王" 9  * @author DELL10  *11  */12 public class FindShuiWang {13     /**14      * 找到发帖"水王"的ID15      * @param ID 所有帖子ID组成的数组16      * @return "水王"的ID17      */18     public static long find(long ID[]){19         Map
     
       map = new HashMap
      
       ();//存储ID和它出现的次数20         int temp,max=0;21         long king=0; //"水王"ID22         long id;23         //将ID和它出现的次数存入map中24         for(int i=0;i
       
         iterator = map.keySet().iterator(); //ID迭代器33         while(iterator.hasNext()){34             id = iterator.next(); //取出一个id35             temp = map.get(id);  //取出id对应的出现次数36 //            if(temp>max){37 //                max = temp;38 //                king = id;39 //            }40             if(temp>ID.length/2){41                 king = id;42                 break;43             }44         }45         return king;46     }47     public static void main(String[] args) {48         long ID[] = {123456,12401645,1324667,123456,123456};49         System.out.println("\"水王\"ID为："+find(ID));50     }51 52 }

程序运行结果如下：

"水王"ID为：123456

扩展问题

　　随着Tango的发展，管理员发现，"超级水王"没有了。统计结果表明，有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？

解答思路同上，代码如下：

1 package chapter2shuzizhimei.findshuiwang; 2  3 import java.util.HashMap; 4 import java.util.Iterator; 5 import java.util.Map; 6  7 /** 8  * 寻找发帖"水王" 9  * 扩展问题10  * @author DELL11  *12  */13 public class FindShuiWang1 {14     /**15      * 找到发帖"水王"的ID16      * @param ID 所有帖子ID组成的数组17      * @return "水王"的ID18      */19     public static long[] find(long ID[]){20         Map
     
       map = new HashMap
      
       ();//存储ID和它出现的次数21         int temp,j=0;22         long king[]; //"水王"ID23         king = new long[3];24         long id;25         //将ID和它出现的次数存入map中26         for(int i=0;i
       
         iterator = map.keySet().iterator(); //ID迭代器35         while(iterator.hasNext()){36             id = iterator.next(); //取出一个id37             temp = map.get(id);  //取出id对应的出现次数38             if(temp>ID.length/4){39                 king[j] = id;40                 j++;41             }42             if(j==3)43                 break;44         }45         return king;46     }47     public static void main(String[] args) {48         long ID[] = {123456,12401645,1324667,123456,12401645,1324667,123};49         long king[] = find(ID);50         System.out.print("三个\"水王\"ID为：");51         for(int i=0;i<3;i++){52             System.out.print(king[i]+" ");53         }54         System.out.println();55     }56 57 }

程序运行结果如下：

三个"水王"ID为：1324667 12401645 123456

转载于:https://www.cnblogs.com/gaopeng527/p/4615924.html

你可能感兴趣的文章