题目：微软面试题“寻找水王”
要求：
三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。
如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？
设计思想：先将id存入数组a [n]，假设水王的id为a[0],用变量count记录下水王id出现的次数，count初始为1，遍历id的数组，遇到相同的id令count加一，不同的就减一，由于真正水王的帖子超过了总数目的一半，所以假的水王count最终一定会减到0，当count为0时，再假设水王的id为a [1],以此类推，返回count不为零的id，即是水王的id。
代码实现：
package jin14; import java.util.Scanner; public class Shui { public static int Find(int a[],int n){ int num=a[0];//设水王的id为num int count=1;//记录次数 for (int i=0;i<n;i++){ if (count==0){//不是水王会减到0，减为0换一个。 num=a[i]; count=1; } else if (a[i]==num) { count++;//相同相加 } else { count--;//不同相减 } } return num; } //输出 public static void main(String[] args) { System.out.println("请输入帖子数量"); Scanner cin=new Scanner(System.in); int n=cin. nextInt();//数量 System.out.println("请输入帖子id"); int a[]=new int[n]; for (int i=0;i<n;i++) a[i]=cin.nextInt(); System.out.println("水王的id为："); System.out.println(Find(a,n)); cin.close(); } }
实现截图：
个人总结：要阔宽思路，敢于思考，在老师的提示下我才了解到“水王发帖数目超过了帖子数目的一半。”这句话的作用，水王不怕删除，利用这个特点，完全可以只用一个循环就可以找出水王。
---恢复内容结束---
原文：https://www.cnblogs.com/wxy2000/p/10961037.html