方法1:哈希表
时间复杂度:$O(n)$
空间复杂度:$O(n)$
解题思路
其实就是寻找出现次数最多的元素。因为已经假定了必然有一个多数元素存在,而且超过n/2意味着只能出现一次,那么这样的值有且仅有一个,且就是出现次数最多的那个。
Java 代码
class Solution {
private Map<Integer, Integer> countNums(int[] nums){
Map<Integer, Integer> counts = new HashMap<>();
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> MaxEntry = null;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (MaxEntry == null || entry.getValue() > MaxEntry.getValue()) {
MaxEntry = entry;
}
}
return MaxEntry.getKey();
}
}