多數元素
投票法
讓你找到序列中出現超過二分之一的元素，一定要記住這個規則。
記錄兩個值val和cnt，剛開始val為任意數，cnt=0。
如果cnt是0，就把當前val = num。接下來判斷，ifnum == val，則cnt ++，elsecnt--。最后的val就是出現次數超過二分之一的數。
原理
你可以以‘對沖’思路去想，讓你找到出現超過二分之一的數，把這個target當做一只軍隊，然后剩下的普通num去當做另一只軍隊，目標數target去跟普通的num去‘對沖’，一換一，最后留下來的肯定是答案。
我上面舉得例子是我們上來分出來了哪些是target哪些是普通num，但是代碼里怎么分辨呢？其實不用分辨，如果我們看錯了target，那么自然會被消耗掉，被消耗掉了會有其他的target頂上，只有真正的target頂上才能完成
class Solution {public int majorityElement(int[] nums) {int n = nums.length;int res = 0;int vote = 0;for(int num:nums){if(vote==0) res = num;if(num == res) vote++;else vote--;}return res;}
}
