題目

給定一個大小為?n?的數組?nums?，返回其中的多數元素。多數元素是指在數組中出現次數?大于?? n/2 ??的元素。

你可以假設數組是非空的，并且給定的數組總是存在多數元素。

示例?1：

輸入：nums = [3,2,3]
輸出：3

示例?2：

輸入：nums = [2,2,1,1,1,2,2]
輸出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

進階：嘗試設計時間復雜度為 O(n)、空間復雜度為 O(1) 的算法解決此問題。

題解

class Solution(object):def majorityElement(self, nums):""":type nums: List[int]:rtype: int"""n=len(nums)dic={}for i in nums:if i in dic:dic[i]+=1else:dic[i]=1for j in dic:if dic[j]>(n/2):return j

代碼說明

1.統計元素出現次數：

使用字典?dic?統計每個元素的出現次數。

如果元素?num?已經在字典中，增加其計數；否則，將其添加到字典中并初始化計數為

2.找到多數元素：

遍歷字典?dic，找到出現次數超過?n/2?的元素，并返回該元素。