题目描述
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:nums = [3,2,3]
输出:3
示例 2:
输入:nums = [2,2,1,1,1,2,2]
输出:2
提示:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
分析
这道题可以使用哈希表,还是将重复出现的次数记录下来,最后返回遍历的值即可。
代码实现
class Solution:
def majorityElement(self, nums: List[int]) -> int:
degree = len(nums) // 2
map = {}
for num in nums:
if not map.get(num):
map[num] = 1
else:
map[num] += 1
for key, value in map.items():
if value > degree:
return key
总结
哈希表有着很广泛的应用,能大大降低我们算法的时间复杂度!
来源链接:https://www.cnblogs.com/wephiles/p/18772919
© 版权声明
本站所有资源来自于网络,仅供学习与参考,请勿用于商业用途,否则产生的一切后果将由您(转载者)自己承担!
如有侵犯您的版权,请及时联系3500663466#qq.com(#换@),我们将第一时间删除本站数据。
如有侵犯您的版权,请及时联系3500663466#qq.com(#换@),我们将第一时间删除本站数据。
THE END
暂无评论内容