水王2.0

问题描述：

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？(参考核心代码) 随着论坛的发展，管理员发现水王没有了，但是统计结果表明，有三个发帖很多的ID。据统计他们的发帖数量超过了1/4，你能从发帖列表中快速找到他们吗？

要求将设计思想、代码实现、实现截图、个人总结以博文的形式发表。

设计思想：

还是按照第一次找水王的思路来就可以啦，不过这次的返回值是三个，需要用到数组来解决，nTimes 的3个元素分别对应当前遍历过的3个ID出现的个数。如果遍历中有某个ID不同于这3个当前ID，我们就判断当前3个ID是否有某个的nTimes为0，如果有，那这个新遍历的ID就取而代之，并赋1 为它的遍历数（即nTimes减1），如果当前3个ID的nTimes皆不为0，则3个ID的nTimes皆减去1，这也就是解决本文题的关键了。由于非水王ID不满总帖数的1/4,与上题思路相同，所遍历ID与当前3个ID不同时，就一同抵消（即3个当前ID的nTimes值减1），最终留下来的3个当前ID总会是3个超过1/4的水王ID。

代码实现：

  1 package test;
  2 
  3 public class A 
  4 {
  5     
  6      static int[] ID =new int[100];
  7                
  8      int Rand()//生成0-1内的随机数
  9      {
 10         java.util.Random random=new java.util.Random();// 定义随机类
 11         int result=random.nextInt(4);                  // 返回[0,4)集合中的整数，不包括4
 12         return result;
 13      }
 14                
 15      void FirstC()//初始化数组；
 16      {
 17          for(int i=0;i<100;i++)
 18          {
 19              if(Rand()==0)
 20              {
 21                  ID[i]=50;//水王一号的ID
 22              }
 23              else if(Rand()==1)
 24              { 
 25                  ID[i]=60;//水王二号的ID
 26              }
 27              else if(Rand()==2)
 28              {
 29                  ID[i]=70;//水王三号的ID
 30              }
 31              else
 32              {
 33                   ID[i]=i;
 34              }
 35                       
 36          }
 37               
 38      }
 39                
 40      void Out()
 41      {
 42          System.out.println("以下是水贴的ID单");
 43          for(int i=1;i<=ID.length;i++)
 44          {
 45              System.out.print(ID[i-1]+" ");
 46              if(i%10==0)
 47              {
 48                 System.out.print("
");
 49              }
 50          }
 51      }
 52               
 53      int Serch()//思想实现部分
 54      {
 55          int candIDate=50;
 56          int ntimes,i;
 57          for(i = ntimes = 0;i<ID.length;i++)
 58          {
 59              if(ntimes == 0)
 60              {
 61                  candIDate = ID[i];
 62                  ntimes = 1;
 63              }
 64              else
 65              {
 66                  if(candIDate == ID[i])
 67                     ntimes ++;
 68                  else 
 69                     ntimes --;
 70              }
 71          }
 72                   return candIDate;
 73      }
 74               
 75      public static int[]  Serchs(int[] ID)
 76      {
 77          if(ID == null) return null;  
 78          int candate0= 0;  
 79          int candate1= 0;  
 80          int candate2= 0;  
 81          int times0 = 0;  
 82          int times1 = 0;  
 83          int times2 = 0;  
 84          int len = ID.length;  
 85          for(int i =0;i<len;i++)
 86          {  
 87              if(times0==0&&ID[i]!=candate1&&ID[i]!=candate2)
 88              {  
 89                  candate0=ID[i];  
 90                  times0++;  
 91              }  
 92              else if(times1==0&&ID[i]!=candate0&&ID[i]!=candate2)
 93              {  
 94                  candate1=ID[i];  
 95                  times1++;  
 96              }  
 97              else if(times2==0&&ID[i]!=candate0&&ID[i]!=candate1)
 98              {  
 99                  candate2=ID[i];  
100                  times2++;  
101              }  
102              else if(ID[i]!=candate1&&ID[i]!=candate0&&ID[i]!=candate2)
103              {  
104                  times0--;  
105                  times1--;  
106                  times2--;  
107              }  
108              else if(ID[i]==candate0)  
109                  times0++;  
110              else if(ID[i]==candate1)  
111                  times1++;  
112              else if(ID[i]==candate2)  
113                  times2++;  
114          }  
115          int[] result = {candate0,candate1,candate2};  
116          return result;  
117      }  
118               
119      public static void main(String[] args) 
120      {
121          A  a = new A();
122          a.FirstC();
123          a.Out();
124          int[] results=new int[3];
125          results=A.Serchs(ID);
126          System.out.println("三个水王的ID分别是");
127          for(int i=0;i<3;i++)
128          {
129               System.out.println("第"+(i+1)+"个水王的ID是"+results[i]);
130          }
131                  
132     }
133 }

实现截图：

当把水王id变为1，99，3时

结果

个人总结：

循环多的时候应该检查层级关系，注意问题之间的类比