☆打卡算法☆LeetCode 169. 多数元素 算法解析
☆打卡算法☆LeetCode 169. 多数元素 算法解析
恬静的小魔龙
发布于 2022-08-07 10:43:18
发布于 2022-08-07 10:43:18
一、题目
1、算法题目
“给定一个数组，返回其中的多数元素。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入： nums = [3,2,3]
输出： 3示例 2：
输入： nums = [2,2,1,1,1,2,2]
输出： 2二、解题
1、思路分析
这道题要求出出现次数大于n/2的元素，暴力方法可以使用遍历美剧数组中的每个元素，再遍历一遍数组统计其出现次数。
但是这个方法的时间复杂度为O(n2)，与题意不符。需要将时间复杂度降到O(n2)以下。
容易想到的可以使用哈希表，去掉一层遍历，将时间复杂度降到O(n)。
2、代码实现
代码参考：
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();
}
}
image.png
3、时间复杂度
时间复杂度：O(n)
其中n是数组nums的长度，遍历一遍数组，在遍历结束对哈希表进行遍历，因为哈希表占用的空间为O(n)，因此总时间复杂度为O(n)。
空间复杂度：O(n)
其中n是数组nums的长度。
三、总结
使用哈希表来存储每个元素以及出现的次数。
对于哈希表中每个键值对，键表示元素，值表示次数。
用循环遍历数组，并将数组中的每个元素加入哈希表中。
遍历哈希表中所有键值对，返回值最大的键。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录