image.png
解法
神奇的解法上煤，因為要返回的數(shù)，要超過半數(shù)著淆，所以相同加1劫狠，不同減1，最終count應(yīng)該是大于0的牧抽，所以可以這樣去求解嘉熊。
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int candidate = nums[0];
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += candidate == num ? 1 : -1;
}
return candidate;
}
}
剩下的常規(guī)解法遥赚，可以用map去維護(hù)出現(xiàn)的次數(shù)扬舒，發(fā)現(xiàn)超過半數(shù)的直接返回就好啦，不過這樣空間復(fù)雜度不是O(1)
