给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
解法一:
满足题干要求的众数若存在,则仅可能存在一个
- 用dict来存储每个数字出现的次数
- 根据出现次数排序
- 判断出现次数最多的元素,其出现次数是否超过len/2 +1
python代码:
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
cnt = length // 2 + 1
cnt_dict = {}
for i in nums:
if i in cnt_dict:
cnt_dict[i] += 1
else:
cnt_dict[i] = 1
cnt_dict = sorted(cnt_dict.items(), key=lambda x:x[1])
print(cnt_dict)
if cnt_dict[-1][1] >= cnt:
return cnt_dict[-1][0]
else:
return 0
注意
- python中的sorted()函数可以对list和dict排序,对list排序比较简单:
x = [1,3,4,2]
y = sorted(x)
输出为
y = [1,2,3,4]
对dict排序时需要制定按照哪个值来排序,并且返回的是一个list,详见:
https://www.runoob.com/python/python-func-sorted.html
值得注意的是,为了方便起见,这里直接用了dict.items()将dict转换成了一个list
dict = { 'one': 1, 'two': 2}
dict.items() = [('one',1), ('two',2)]
解法二:
众数出现的次数一定大于其他所有元素出现次数之和
- 遍历数组,记录两个数res,cnt
- 若当前元素和res相等,则cnt + 1,不相等则 cnt - 1, cnt等于0时,res等于当前元素
- 遍历结束后res的值可能为众数,但还需要检查是否满足大于 length/2(因为有可能相等,则不满足)
python代码
class Solution(object):
def majorityElement(self, nums):
cnt = 0
res = nums[0]
for i in range(len(nums)):
if cnt == 0:
res = nums[i]
cnt = 1
elif res == nums[i]:
cnt += 1
elif res != nums[i]:
cnt -=1
# 判断出现次数最多元素的次数是否满足题干要求
count = 0
for i in range(len(nums)):
if nums[i] == res:
count +=1
if count > len(nums) / 2:
return res
else:
return 0