14周课堂测试---找水王

偏执的太偏执、 2021-12-18 17:27 289阅读 0赞

**问题概述：寻找发帖人中的水王·---发帖超过一半**

**问题抽象化：寻找数组中出现超过一半的数字**

**要求:只使用一次循环结构**

解决思路：将出现的数组元素遍历两两比较，相同则加一，不同则减一，当减为0时更换元素

由于水王出现超过一半，故当遍历完成后剩下的就是水王。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 package zhaoshuiwang;
     2 
     3 import java.util.Scanner;
     4 
     5 public class water {
     6       public static void main(String[] args) {
     7           System.out.println("请输入帖子数目");
     8         Scanner sc=new Scanner(System.in);
     9         int n=sc. nextInt();//数量
    10         System.out.println("请依次输入各个帖子发帖人id");
    11         int a[]=new int[n];
    12         for (int i=0;i<n;i++)
    13          a[i]=sc.nextInt();
    14          System.out.println(Find(a,n));
    15          sc.close();
    16        }
    17 
    18 
    19     //水王pk，相同者+，不同者-，最后剩下水王
    20     public static int Find(int a[],int n){
    21         int king=a[0];
    22         int number=1;
    23         for (int i=0;i<n;i++){
    24             if (number==0){
    25                 king=a[i];
    26                 number=1;
    27             }else
    28             if (a[i]==king){
    29                 number++;
    30             }else{
    31                 number--;
    32             }
    33         }
    34         return king;
    35     }
    36 
    37 }

water

转载于:https://www.cnblogs.com/yeshenfeng/p/10951103.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211218/ed88b0a480564e68932c2a3d8fc5a33f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，289人围观）

还没有评论，来说两句吧...

相关阅读

相关寻找发帖“水王“（分治法）

问题描述：有某一论坛，其中有一发帖水王，不但喜欢发帖，还会回复其他ID发的每个帖子。“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表

太过爱你忘了你带给我的痛/ 2022年11月13日 04:29/ 0 赞/ 172 阅读

相关课堂练习-找水王

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目

ゝ一纸荒年。/ 2022年10月03日 00:42/ 0 赞/ 181 阅读

相关水王问题java解法

核心思想就是删除相应的比例，剩着为王，所占比例可以推广！ public class KingOfWater { public static voi

偏执的太偏执、/ 2022年09月25日 04:22/ 0 赞/ 171 阅读

相关 SOJ--4389: 川大贴吧水王

描述 \_L的室友HZ喜欢在川大贴吧上发帖，据传说，HZ在川大贴吧上发的贴子数已经超过了该贴吧贴子总数的一半，被江湖人封为川大贴吧水王，你能帮\_L迅速找出这位川大

墨蓝/ 2022年08月06日 04:21/ 0 赞/ 246 阅读

相关课堂测试——增加信息

一、程序设计思想按照JSP+Servlet+JavaBean的开发模式，将编码任务划分成以下部分： JSP：页面上显示输入框和提交按钮，并且在界面上插入JavaScrip

ゝ一世哀愁。/ 2021年12月24日 02:13/ 0 赞/ 261 阅读

相关找水王

一、题目　　有一个大“水王”，他不仅喜欢发贴，还会回复其他ID发的每个帖子。该“水王”发帖数目超过了帖子总数的一半。如果有当前论坛上所有帖子（包括回帖）的列表，其中帖子作者

深藏阁楼爱情的钟/ 2021年12月22日 03:39/ 0 赞/ 258 阅读

相关 14周课堂测试---找水王

问题概述：寻找发帖人中的水王·---发帖超过一半问题抽象化：寻找数组中出现超过一半的数字要求:只使用一次循环结构解决思路：将出现的数组元素遍历两两比较，相同则加一，

偏执的太偏执、/ 2021年12月18日 17:27/ 0 赞/ 290 阅读

相关找水王

要求：三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过

Love The Way You Lie/ 2021年11月19日 13:34/ 0 赞/ 319 阅读

相关找到“水王”

1、问题描述：三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目

た入场券/ 2021年11月09日 02:14/ 0 赞/ 349 阅读

相关关于找水王的思路

关于上节课老师留的作业，从帖子中寻找发帖数超过一半的水王。我的思路是让计算机从开头开始遍历，不同发帖人的id可以相互抵消，遇到相同的id就保留，这样，当程序运行一般时，剩余

﹏ヽ暗。殇╰゛Y/ 2021年09月20日 10:02/ 0 赞/ 325 阅读