UNIN队设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水,传说在论坛上有一个“水王”,他不但喜欢发帖,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。
如果你有一张当前论坛的帖子(包括回帖)列表,其中帖子的作者的ID也在其中,你能快速的找到这个传说中的水王吗?
分析:该题目中有一关键信息,水王发帖量超过总贴量的一半,如果循环一次的话,我们可以通过如下方式找到水王:
首先,我们可以比较前两行信息,如果id相同,则都保持不变,再与下一行id比较;如果前两行id不相同,则删除这两行的信息,再比较后面两行信息的id,不断重复这个过程,把列表中总数降低,最后剩下的肯定是水王的ID。
代码实现:
package find; import javax.security.auth.x500.X500Principal; public class findsw { public static int findshuiwang(int[] id)//找水王 { int n = id.length; int shuiwang = 0; int count=0; for(int i=0;i<n;i++) { if(count == 0) { shuiwang = id[i]; count = 1; } else { if(shuiwang == id[i]) count ++; else count --; } } return shuiwang; } public static void main(String[] args) { int []a={2,2,1,1,4,1,2,5,1,7,1,1,1,1,2};//模拟发帖人的id,其中水王是1 System.out.println("水王是"+findshuiwang(a)); } }