“给定一个数组,返回其中的多数元素。”
题目链接:
来源:力扣(LeetCode)
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: nums = [3,2,3]
输出: 3
示例 2:
输入: nums = [2,2,1,1,1,2,2]
输出: 2
这道题要求出出现次数大于n/2的元素,暴力方法可以使用遍历美剧数组中的每个元素,再遍历一遍数组统计其出现次数。
但是这个方法的时间复杂度为O(n2),与题意不符。需要将时间复杂度降到O(n2)以下。
容易想到的可以使用哈希表,去掉一层遍历,将时间复杂度降到O(n)。
代码参考:
class Solution {
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)
其中n是数组nums的长度,遍历一遍数组,在遍历结束对哈希表进行遍历,因为哈希表占用的空间为O(n),因此总时间复杂度为O(n)。
空间复杂度:O(n)
其中n是数组nums的长度。
使用哈希表来存储每个元素以及出现的次数。
对于哈希表中每个键值对,键表示元素,值表示次数。
用循环遍历数组,并将数组中的每个元素加入哈希表中。
遍历哈希表中所有键值对,返回值最大的键。