多数元素——面试经典150题（力扣）

题目

给定一个大小为 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 进阶： 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

题解

class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n=len(nums)
dic={}
for i in nums:
if i in dic:
dic[i]+=1
else:
dic[i]=1
for j in dic:
if dic[j]>(n/2):
return j

代码说明

1.统计元素出现次数 ： 使用字典 dic 统计每个元素的出现次数。 如果元素 num 已经在字典中，增加其计数；否则，将其添加到字典中并初始化计数为 2.找到多数元素 ： 遍历字典 dic ，找到出现次数超过 n/2 的元素，并返回该元素。