劍指 Offer 39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。

?

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

?

示例 1:

輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

輸出: 2

我是用的字典存放的，速度比較慢。

之前也試過排序，但是有點寄。。

class?Solution:

????def?majorityElement(self,?nums:?List[int])?->?int:

????????if?not?nums:return?None

????????dict={}

????????totallen=len(nums)

????????for?i?in?range(totallen):

????????????if?not?nums[i]?in?dict:

????????????????dict[nums[i]]=1

????????????????if?dict[nums[i]]>(totallen//2):

????????????????????return?nums[i]

????????????else:

????????????????dict[nums[i]]+=1

????????????????if?dict[nums[i]]>(totallen//2):

????????????????????return?nums[i]

????????return?-1

然后用字典排序的話會快一點（返回第一個key搜了好久，嗚嗚嗚我好菜啊，原來只要當(dāng)成二維數(shù)組就行了）

然后dict的排序的話麻煩一點，用lambda表達(dá)式限定條件

x[1]表示按照value值排序，reverse表示從大帶小排序。

看了看題解，還有摩爾排序法，搬過來~

若記?眾數(shù)?的票數(shù)為?+1?，非眾數(shù)?的票數(shù)為??1?，則一定有所有數(shù)字的?票數(shù)和?>0?。

class Solution:

? ? def majorityElement(self, nums: List[int]) -> int:

? ? ? ? votes = 0

? ? ? ? for num in nums:

? ? ? ? ? ? if votes == 0: x = num

? ? ? ? ? ? votes += 1 if num == x else -1

? ? ? ? return x