LeetCode Hot100 169.多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

方法一：哈希表


class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int times = map.getOrDefault(nums[i], 0) + 1;
            if (times > (n / 2))
                return nums[i];
            map.put(nums[i], times);
        }
        return -1;
    }
}

时间复杂度 o( n ) 空间复杂度 o( n )

方法二：摩尔投票算法

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int count = 0, ans = -1;
        for (int i = 0; i < n; i++) {
            if (count == 0) {
                ans = nums[i];
                count++;
            }
            else if (nums[i] == ans)
                count++;
            else 
                count--;
        }
        return ans;
    }
}