題目描述
給定一個大小為 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
解答方法
方法一：哈希表
思路
代碼
class Solution:
def majorityElement(self, nums: List[int]) -> int:
dic = {}
for num in nums:
if num in dic:
dic[num] += 1
else:
dic[num] = 1
for i in dic:
if dic[i] > len(nums) // 2:
return i
時間復雜度
O(n)
空間復雜度
O(n)
方法二：摩爾投票法
思路
通過不斷消除不同元素直到?jīng)]有不同元素矗烛，剩下的元素就是我們要找的元素玫镐。
代碼
class Solution:
def majorityElement(self, nums: List[int]) -> int:
cnt = 0
for num in nums:
if cnt == 0:
res = num
if res == num:
cnt +=1
else:
cnt -= 1
return res
時間復雜度
O(n)
空間復雜度
O(1)
