169. Majority Element

题目

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.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

题目大意

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

解题思路

思路：这个问题要解决什么
统计每个元素出现的次数—>使用什么结构，既能存储元素又能存储次数—>Map
找 Map中value最大的key–>将entrySet放入List，自定义排序

代码

public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.get(num) == null) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }
        List<Map.Entry<Integer,Integer>> array=new ArrayList<>(map.entrySet());
        Collections.sort(array,((o1, o2) -> o1.getValue()-o2.getValue()));
        return array.get(array.size()-1).getKey();
    }

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们遍历数组 nums 一次，对于 nums 中的每一个元素，将其插入哈希表都只需要常数时间。如果在遍历时没有维护最大值，在遍历结束后还需要对哈希表进行遍历，因为哈希表中占用的空间为 O(n)（可参考下文的空间复杂度分析），那么遍历的时间不会超过 O(n)。因此总时间复杂度为 O(n)。

空间复杂度：O(n)。哈希表最多包含n-n/2个键值对。