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

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

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

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

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

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

 

14周课堂测试---找水王
 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

 

上一篇:LeetCode-365 Water and Jug Problem


下一篇:前端路由(七)-编程式导航——通过js方法实现路由跳转 & 获取编程式导航传递的参数-props.location.state & 如果组件不是路由组件-必须使用withRouter包裹原始的组件