方法一：是利用的是“得到数组中第k大的数字”算法。即快排的partition方法或者大根堆方法。
快排的partition方法
大根堆方法

class Solution {
    Random random=new Random();
    public int majorityElement(int[] nums) {
        return quickSelect(nums,0,nums.length-1,nums.length/2);
    }
    public int quickSelect(int[] a,int left,int right,int index){
        int ran=random.nextInt(right-left+1)+left;
        swap(a,ran,left);
        int i=left;
        int j=right;
        int temp=a[left];
        while(i<j){
            while(temp<=a[j]&&i<j){
                --j;
            }
            while(a[i]<=temp&&i<j){
                ++i;
            }
            if(i<j){
                swap(a,j,i);
            }
        }
        swap(a,left,i);
        if(i==index){
            return a[i];
        }else{
            return i<index?quickSelect(a,i+1,right,index):quickSelect(a,left,i-1,index);
        }
    }
    public void swap(int[] a,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

方法2：根据特点来计算

class Solution {
    Random random=new Random();
    public int majorityElement(int[] nums) {
        int time=0;
        int result=0;
        for(int i=0;i<nums.length;++i){
            if(time==0){
                result=nums[i];
                time=1;
            }else if(nums[i]==result){
                ++time;
            }else{
                --time;
            }
        }
        return result;
    }
}