給定一個大小為 n 的數(shù)組澎粟，找到其中的多數(shù)元素奇昙。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。
你可以假設(shè)數(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;
}
}
