一个有挑战性的算法题!!!

Question

数组T[n]，找出他的主元素，要求时间复杂度为O(n);
主元素：在T[n]中重复个数迢过n/2的数

Answer 1

找第n/2 和n-n/2大的数，然后检查这两个哪个是

Answer 2

找第n/2 和n-n/2大的数，然后检查这两个哪个是
这个算法，很明显的不对，举个反例：
2 3 4 5 6 6 6 6 6
按题意结果应该是6
而按这个算法则是在2和3选一个

Answer 3

int t[]={14,4,22,3,4,5,5,4,5,4,5,4,5,4,4};    Arrays.sort(t);    System.out.println(t[t.length/2]);

Answer 4

sort(t);不用复杂度的吗？这样当然不行了

Answer 5

设T[0:n-1]是n个元素的数组。对任意一个元素x，设S(x)={i|T[i]=x}。当|S(x)|〉n/2时，称x为T的主元素。设计一个线性时间算法，确定T[0:n-1]是否有一个主元素。
b) 分析
通过对问题目的性的研究，可以得到这样的一个结论：
在元素数组中，删去不同的两个元素，数组的主元素保持不变。
按照这样的思路，我们可以不断缩小问题的规模，最终使问题得解：
设置变量Seed用于存储当前候选元素，初始化为数组首元素a[0]；
设置变量count用于控制候选元素，初始化为1；
从第二个元素a[1]开始遍历数组，并与Seed相比较：
相同，则count加1，读入下一个元素；
不同，则count减1，读入下一个元素：相当于删去两个不同元素，缩小问题规模；
如果count小于0则Seed不是主元素候选，读入下一个元素，count加1。
这样一次遍历之后，得到的Seed就是主元素的候选；
但因为最终得到的Seed元素有可能是序列最末位的两个元素之一，所以还需要验证。
我们再次遍历数组，得到Seed出现的次数，与总数的一半比较来验证。

Answer 6

/**判断输入的数列是否有主元素
      */ 
     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;    
         
     } 
}