42_数组中出现次数超过一半的数字

要求：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：
方法一：摩尔投票法，如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。
votes表明当前值出现的次数，如果下一个值和当前值相同那么votes++；如果不同votes--，减到0的时候就要更换新的众数x值了，因为如果存在超过数组长度一半的值，那么最后众数x一定会是该值。

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}

方法二：使用hashset对数组进行去重，然后对去重后的数值进行遍历统计数值出现的次数。

class Solution {
    public int majorityElement(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int len = nums.length;
        int x=0;
        for(int i=0;i<len;i++){
            if(!set.contains(nums[i]))set.add(nums[i]);
        }
        for(int s: set){
            int n=0;
            for(int j=0; j<len;j++){
                if(nums[j]==s)n++;
            }
            if(n>(len/2))return s;
        }
        return x;
    }
}