給定一個大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。

你可以假設數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

示例 1:
輸入: [3,2,3]
輸出: 3

示例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2

3種方法：
1.hashmap
2.排序 ，取中間
3.摩爾排序法（這個為什么能成功呢？ 因為數(shù)量多的總能打敗數(shù)量少的，多數(shù)元素的個數(shù)-少量元素的個數(shù)>=1，多數(shù)元素一換一少數(shù)元素，最終還是剩下多數(shù)的）

class Solution {
    public int majorityElement(int[] nums) {
        int cadidate = 0;
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            if(count == 0){
                cadidate = nums[i];
            }
            count += (cadidate == nums[i]) ? 1 : -1;
        }
        return cadidate;
    }
}