leetcode講解–169. Majority Element

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

題目地址

唉,看到這題就想起了,當年,青蔥歲月,菜雞的我做阿里的筆試題,對的,就是這題。當時題目改成了小明收紅包,找出現次數超過一般的那個紅包,要求線性時間複雜度,也就是說不能用排序(排序演算法最優情況是:O(nlogn))。

出現次數超過一半的那個數,我們怎麼在O(n)時間複雜度內把它揪出來,我教你:大浪淘沙法,是金子總會發光法,我要打十個法(意思就是,這一個數就能幹翻全場剩下的所有數,是不是?因為它超過一半啊)。我們來想象一下:我們遍歷這個陣列的時候,定義一個count用來計數,這個超過一半的數,它遇到自己就給count加1,遇到不是自己的數,就給count減1,最後會怎樣呢,count肯定大於0吶,因為這個數的個數超過一半。好,進一步的,我們先隨便找個數當這個老大(個數超過一半),如果它的個數不超過一半,就會在相消中時count為0,那麼就把它換掉,最後剩下的那個就是,個數超過一半的那個數了。

程式碼如下:

class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = 1
n = nums[0]
for x in range(1, len(nums)):
if count == 0:
n = nums[x]
count  = 1
else:
if nums[x] == n:
count  = 1
else:
count -= 1
return n

超過一半吶,多麼重的一條資訊,稍微想想就知道,用相消法都能消出那個數,跟那個用異或消出只出現一次的數(其它的數都是成對的,就是都恰好有兩個)是不是異曲同工吶,嗯還是扯得有點遠。

另外這個題在leetcode上的難度是easy哦,好傷心啊,當初的我連這題都沒想出解法,真是夠年輕啊。

相關文章

程式語言 最新文章