编程之美2.3-发帖水王扩展问题

有3个发帖最多的ID，他们发帖数目都超过了帖子总数目的1/4，从发帖ID列表中快速找出这3个ID

 

/**
 * 维护3个ID数据结构，里面name字段存放ID，count是一个计数器，
 * 遍历ID列表时，如果发现一个ID，与其中一个数据结构的name字段相等，这个数据结构的count++
 * 如果发现一个新的ID没有被这3个数据结构记录，那么，如果这3个数据结构中，有一个的count字段为0，则把这个新ID付给这个数据结构的name
 * 同时，他的count+1；反之如果没有发现count为0的数据结构，则把3个数据结构的count都减1。
 * @author Iam42
 */
public class Id {
	public Id(){
		count=0;
		name="";
	}
	
	public int count;
	public String name;
}

 

/**
 * 只需要遍历一次ID列表，没遍历到一个元素就对定义的3个数据结构进行相关的操作
 * 当列表遍历完毕后，三个数据结构里的name字段就是3个发帖水王
 * @author Iam42
 */
public class CatchID {


	public static void main(String[] args) {
		String[] idlist={"a","a","d","d","a","b","d","a","b","d","d","d","a","b","c","a","c","b","a","b"};
		
		Id id1 = new Id();
		Id id2 = new Id();
		Id id3 = new Id();
		
		for(int i=0 ; i<20 ; i++){
		    if(id1.name.equals(idlist[i])){
		    	id1.count++;
		    }else if(id2.name.equals(idlist[i])){
		    	id2.count++;
		    }else if(id3.name.equals(idlist[i])){
		    	id3.count++;
		    }else if(id1.count==0){
				id1.name=idlist[i];
				id1.count++;
			}else if(id2.count==0){
				id2.name=idlist[i];
				id2.count++;
			}else if(id3.count==0){
				id3.name=idlist[i];
				id3.count++;
			}else{
				id1.count--;
				id2.count--;
				id3.count--;
			}
		}

		System.out.println(id1.name);
		System.out.println(id2.name);
		System.out.println(id3.name);
	}
}