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>>(){@Overridepublic 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 的用户。还行，不用继续优化了。