import javax.swing.*; 
 
/** 问题:设T[0:n-1]是n个元素的数组。对任意一个元素x， 
 *设S(x)={i|T[i]=x}。当|S(x)|〉n/2时，称x为T的主元素。 
 *设计一个线性时间算法，确定T[0:n-1]是否有一个主元素。 
 */ 
public class Master 
{ 
     
     final static int maxInput = 100;   //最大处理序列为100 
     /**主程序接受一组整数值,调用hasMaster()判断是否存在主元素。 
     */ 
     public static void main(String args[]) 
     { 
         int data[] = new int[100]; 
         int nInput=0; 
      
         String input,msg; 
      
         try 
         { 
             for(int i=0; i<maxInput; i++) 
             { 
                input =  
                    JOptionPane.showInputDialog
                         ("请输入数据 #"+(i+1)+"\n空白结束"); 
                 
                if((input.trim()).length()==0)  //空白结束 
                    break; 
                 
                nInput = i+1;       //输入计数 
                 
                data[i] = Integer.parseInt(input); 
         
             }  //end of for 
              
             msg = "输入的数列：\n"; 
             for(int i=0; i<nInput; i++) 
             { 
       
          msg+= data[i]+" "; 
                if(i%10==9) 
                    msg+="\n"; 
             } 
              
             msg+="\n"; 
             msg+=(hasMaster(data,nInput)?"有":"没有"); 
             msg+="主元素。";             
              
              
             JOptionPane.showMessageDialog(null, 
                msg); 
  
          
         } 
         catch (Exception ex) 
         { 
            JOptionPane.showMessageDialog
                            (null,ex.getLocalizedMessage()); 
         }   
     }  
      
     /**判断输入的数列是否有主元素
      */ 
     private static boolean hasMaster(int data[], int n) 
     { 
        int count=0;    //保存计数 
        int seed;       //保存参照元素 
         
        seed = data[0]; 
         
        for(int i=1; i<n; i++) 
        { 
            if(seed == data[i])     //如果数据相同，计数加一 
            { 
                count++; 
            } 
            if(seed == data[i]) 
            { 
                if(count>0) 
      
           { 
                    count--;        //如果数据不同，则计数减一 
                                    //相当于删除两个不同的元素 
                                    //不会对主元素造成影响 
                } 
                else 
                { 
                    seed = data[i]; //计数为零时，seed不可能为主元素 
                                    //读入新数据 
                } 
            } //end of if 
        } //end of for 
         
        //因为最终得到的seed元素有可能是序列最末位的两个元素之一 
        //因此，这里还需要验证 
        count = 0; 
        for(int i=0; i<n; i++) 
        { 
            if (seed == data[i]) 
                count++; 
        } 
         
        if(count>(n/2)) 
        { 
            return true; 
        } 
         
        return false;    
         
     } 
}