給定一個數組（長度為n），找出“多數元素”（出現次數大于n/2），假定數組不為空且“多數元素”一定存在。

思路一：
將數組排序，則最中間的那個數一定是“多數元素”。

時間復雜度：O(n*lgn)

class Solution:def majorityElement(self, nums):""":type nums: List[int]:rtype: int"""nums.sort()return nums[len(nums)//2]

思路二：
使用dict用來記錄數組里每個數出現的次數。
空間復雜度：O(n)，時間復雜度：O(n)

class Solution(object):def majorityElement(self, nums):count = {}for i in nums:if i in count:count[i] += 1else:count[i] = 1return max(count, key=count.get)

• 相關知識點：
  get()：返回指定鍵的值，如果值不在字典中則返回默認值。

總結

以上是生活随笔為你收集整理的10/100. Majority Element的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。