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

寻找发帖“水王”

问题描述

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

解法

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

package chapter2shuzizhimei.findshuiwang;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 寻找发帖"水王"
 * @author DELL
 *
 */
public class FindShuiWang {
    /**
     * 找到发帖"水王"的ID
     * @param ID 所有帖子ID组成的数组
     * @return "水王"的ID
     */
    public static long find(long ID[]){
        Map<Long,Integer> map = new HashMap<Long,Integer>();//存储ID和它出现的次数
        int temp,max=0;
        long king=0; //"水王"ID
        long id;
        //将ID和它出现的次数存入map中
        for(int i=0;i<ID.length;i++){
            if(map.containsKey(ID[i])){
                temp = map.get(ID[i])+1;
                map.put(ID[i], temp);
            }else{
                map.put(ID[i], 1);
            }
        }
        Iterator<Long> iterator = map.keySet().iterator(); //ID迭代器
        while(iterator.hasNext()){
            id = iterator.next(); //取出一个id
            temp = map.get(id);  //取出id对应的出现次数
//            if(temp>max){
//                max = temp;
//                king = id;
//            }
            if(temp>ID.length/2){
                king = id;
                break;
            }
        }
        return king;
    }
    public static void main(String[] args) {
        long ID[] = {123456,12401645,1324667,123456,123456};
        System.out.println(""水王"ID为："+find(ID));
    }

}

程序运行结果如下：

"水王"ID为：123456

扩展问题

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

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

package chapter2shuzizhimei.findshuiwang;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 寻找发帖"水王"
 * 扩展问题
 * @author DELL
 *
 */
public class FindShuiWang1 {
    /**
     * 找到发帖"水王"的ID
     * @param ID 所有帖子ID组成的数组
     * @return "水王"的ID
     */
    public static long[] find(long ID[]){
        Map<Long,Integer> map = new HashMap<Long,Integer>();//存储ID和它出现的次数
        int temp,j=0;
        long king[]; //"水王"ID
        king = new long[3];
        long id;
        //将ID和它出现的次数存入map中
        for(int i=0;i<ID.length;i++){
            if(map.containsKey(ID[i])){
                temp = map.get(ID[i])+1;
                map.put(ID[i], temp);
            }else{
                map.put(ID[i], 1);
            }
        }
        Iterator<Long> iterator = map.keySet().iterator(); //ID迭代器
        while(iterator.hasNext()){
            id = iterator.next(); //取出一个id
            temp = map.get(id);  //取出id对应的出现次数
            if(temp>ID.length/4){
                king[j] = id;
                j++;
            }
            if(j==3)
                break;
        }
        return king;
    }
    public static void main(String[] args) {
        long ID[] = {123456,12401645,1324667,123456,12401645,1324667,123};
        long king[] = find(ID);
        System.out.print("三个"水王"ID为：");
        for(int i=0;i<3;i++){
            System.out.print(king[i]+" ");
        }
        System.out.println();
    }

}

程序运行结果如下：

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