Majority Element leetcode

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

方法1 : hashmap timeO(n) space O(n)

方法2: 排序 time nlog(n), space O(1)

方法3:vote algorithm time O(n) space O(1)

//1
public class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int s : nums) {
            if (map.containsKey(s)) {
                map.put(s, map.get(s) + 1);
            } else {
                map.put(s, 1);
            }
        }
        for (int s : map.keySet()) {
            if (map.get(s) > nums.length / 2) {
                return s;
            }
        }
        return -1;
    }
}
//2
public class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}
//3
public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int res = 0;
        for (int s : nums) {
            if (count == 0) {
                res = s;
                count ++;
            } else if (count != 0 && s == res) {
                count++;
            } else {
                count--;
            }
        }
        return res;
    }
}