169. 多数元素

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

• 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

哈希计数

利用哈希表记录每个数字出现的次数，然后比较次数大于 n/2 的元素

private Map<Integer, Integer> countNums(int[] nums) {
    Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
    for (int num : nums) {
        if (!counts.containsKey(num)) {
            counts.put(num, 1);
        } else {
            counts.put(num, counts.get(num) + 1);
        }
    }
    return counts;
}

public int majorityElement(int[] nums) {
    Map<Integer, Integer> counts = countNums(nums);

    Map.Entry<Integer, Integer> majorityEntry = null;
    for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
        if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
            majorityEntry = entry;
        }
    }

    return majorityEntry.getKey();
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)