題目
難度：★☆☆☆☆
類型：數(shù)學
給定一個大小為 n 的數(shù)組实愚，找到其中的眾數(shù)腊敲。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素茫负。
你可以假設數(shù)組是非空的忍法，并且給定的數(shù)組總是存在眾數(shù)。
示例
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2
解答
方案1：字典（哈希表）
為了找到出現(xiàn)次數(shù)最多的數(shù)原探，最簡單的邏輯就是統(tǒng)計每次數(shù)字出現(xiàn)的次數(shù)，再拿取出其中出現(xiàn)次數(shù)最多的數(shù)字型型。該方法道理簡單，但是內(nèi)存開銷較大绷落。
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = {}
for num in nums: # 統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù)
if num in count:
count[num] += 1
else:
count[num] = 1
return {v: k for k, v in count.items()}[max(count.values())] # 字典鍵值反轉(zhuǎn)，找到出現(xiàn)次數(shù)最多的數(shù)字
方案2：數(shù)字統(tǒng)計
這道題目所求的眾數(shù)的定義與常規(guī)概念不同的是，這里眾數(shù)的出現(xiàn)次數(shù)要比數(shù)組中其他所有元素要多的蓄氧，根據(jù)這個原理，我們將結果變量（res）初始化為數(shù)組第一個數(shù)蔑担，另外準備一個統(tǒng)計變量（count）啤握，當這個變量遇到和結果相同的數(shù)則加一，否則減一蹲蒲，減為零時更換結果變量為下一個數(shù)届搁，由于眾數(shù)出現(xiàn)次數(shù)多于其他字符，那么數(shù)組遍歷結束后統(tǒng)計變量一定大于零表锻，且此時結果變量中的數(shù)即為眾數(shù)。
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count, res = 0, nums[0] # 初始化計數(shù)器和結果
for i in range(len(nums)-1): # 遍歷數(shù)組中每一個數(shù)
if nums[i] == res: # 如果當前的數(shù)和結果變量相同
count += 1 # 計數(shù)器+1
else: # 否則
count -= 1 # 計數(shù)器-1
if count == 0: # 如果減到了0
res = nums[i+1] # 那么更新結果變量為下一個數(shù)
return res # 返回結果
方案3：排序
這里眾數(shù)的的出現(xiàn)次數(shù)超過其他元素，因此我們將數(shù)據(jù)進行排序后骚腥，最中間的數(shù)字一定是眾數(shù)。
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return nums[len(nums) // 2]
如有疑問或建議，歡迎評論區(qū)留言~
