LeetCode：169.多数元素（哈希表）

题目

第一版

思路

直接开个哈希表，存储每个数组中的数字和对应出现的次数。然后排序后找出对应最大value值的key。

代码

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer>map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            int cnt = map.getOrDefault(nums[i], 0);
            map.put(nums[i],++cnt);
        }
        List<Map.Entry<Integer,Integer>>list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer,Integer>>(){
            @Override
            public int compare(Map.Entry<Integer,Integer> o1, Map.Entry<Integer,Integer> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        Map.Entry<Integer,Integer> last = list.get(list.size()-1);
        return last.getKey(); 
    }
}

效率分析

12ms，击败28.66%使用 Java 的用户。说明还需要优化。

第二版

代码

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer>map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            int cnt = map.getOrDefault(nums[i], 0);
            map.put(nums[i],++cnt);
        }
        int maxcnt = 0;
        int ans=0;
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            if(maxcnt<entry.getValue()){
                ans = entry.getKey();
                maxcnt = entry.getValue();
            }
        }
        return ans;
    }
}

效率分析

11ms，击败32.60%使用 Java 的用户

第三版

思路

直接对原数组进行排序，最后返回下标为数组长度/2的元素即可。（因为是上取整，所以奇数长度的数组也适用，而且题目保证了一定会有一个众数作为答案）。

代码

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

效率分析

2ms，击败66.84%使用 Java 的用户。还行，不用继续优化了。