給定一個大小為 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
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
