找寻发帖“水王”

寻找发帖“水王”

问题：

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

分析与解法：

最直接的方法，我们可以对所有ID排序。然后再扫描一边排好序的ID列表，统计各个ID出现的次数。如果某个ID出现的次数超过总数的一半，那么就输出这个ID。这个算法的时间复杂度为O(N*log2N+N).

如果ID列表已经是有序的，还需要扫描一遍整个列表来统计各个ID出现的次数吗？

如果一个ID出现的次数超过总数的一半，那么无论水王的ID是什么，这个有序ID列表中的第N/2项(从0开始编号)一定会是这个ID。不必扫描列表。如果能够迅速定位到列表中的某一项（比如使用数组来存储列表），除去排序的时间复杂度，后处理需要的时间为O(1).

但上面两种方法都需要先对ID列表进行排序，时间复杂度方面没有本质的改进。能否避免进行排序呢？

如果每次删除两个不同的ID（不管是否包含水王的ID），那么，在剩下的ID列表中，水王ID出现的次数仍然超过总数的一半。可以通过不断重复这个过程，把ID列表中的ID总数降低（转化为更小的问题），从而得到答案。新的思路，避免了排序这个耗时的步骤，总的时间复杂度只有O(N)，且只需要常数的额外内存。

代码清单：

public class beauty_2_3 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] ids = {"ab","ab","dc","ab","aa","ab"};
		System.out.println(find(ids));

	}

	public static String find(String[] id){
		if(id == null){
			System.out.println("请输入id列表");
			return null;
		}			
		int n = id.length;
		String candidate = null;
		int ntimes,i;
		for(i = ntimes = 0;i<n;i++){
			if(ntimes == 0){
				candidate = id[i];
				ntimes = 1;
			}
			else{
				if(candidate == id[i])
					ntimes ++;
				else 
					ntimes --;
			}
		}
		return candidate;
		
		
	}
}