題目描述：
給定一個(gè)大小為 n 的數(shù)組，找到其中的眾數(shù)。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。

思路：

1. Map存每個(gè)數(shù)出現(xiàn)次數(shù)，大于n/2即為眾數(shù)
2. Moore voting alogrithm：每次從數(shù)組中找出一對(duì)不同的元素，將它們從數(shù)組中刪除，直到遍歷完整個(gè)數(shù)組。由于這道題已經(jīng)說(shuō)明一定存在一個(gè)出現(xiàn)次數(shù)超過(guò)一半的元素，所以遍歷完數(shù)組后數(shù)組中一定會(huì)存在至少一個(gè)元素。
3. 分治法，不斷把數(shù)組分成左右兩個(gè)數(shù)組，分別求兩個(gè)數(shù)組的眾數(shù)，如果相等則返回此數(shù)，如果不等則返回兩個(gè)數(shù)組合并后的真正的眾數(shù)。

class Solution {
    public int majorityElement(int[] nums) {
        return find(nums,0,nums.length-1);        
    }
    
        public static int find(int[] nums, int begin, int end){
        if (begin == end)
            return nums[begin];
        else {
            int mid = (begin+end)/2;
            int left = find(nums,begin,mid);
            int right = find(nums,mid+1,end);
 
            if(left == right)//左右兩部分的眾數(shù)相同 則這個(gè)數(shù)是這部分的眾數(shù)
                return left;
            else{//左右兩部分的眾數(shù)不相同 則這兩個(gè)數(shù)都有可能是這部分的眾數(shù)
                //那么遍歷這個(gè)數(shù)組 看一下哪個(gè)數(shù)字的出現(xiàn)頻率高
                int countLeft = 0;
                int countRight = 0;
                for (int i = begin; i <= end; i++)
                    if(nums[i] == left)
                        countLeft++;
                    else if (nums[i] == right)
                        countRight++;
 
                if(countLeft>countRight)
                    return left;
                else
                    return right;
            }
        }
    }
 
    
}