leetcode with python:169. Majority Element

题目:

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than (n / 2) times. You may assume that the majority element always exists in the array.

给定一个长度为n的阵列,返回它的majority element(出现>n/2次的值)

最初想法就是建立一个dictionary纪录各数出现的次数
最后看哪个数出现了n/2次以上即为majority element

class Solution:    def majorityElement(self, nums: List[int]) -> int:        d={}        for i in nums:            if i in d:                d[i]=d[i]+1            else:                d[i]=1        for i in d:            if d[i]>len(nums)/2:                return i

最后执行时间185ms(faster than 81.70%)

不过一个一个计数实在有点慢
后来我想到既然确定majority element会出现n/2次以上
那在阵列为排序阵列的状况下,中间必然为majority element
于是有了以下简短的程式码

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

最后执行时间159ms(faster than 99.16%)

看了讨论区才发现题目其实是要用博耶-摩尔多数投票算法（Boyer–Moore majority vote algorithm）
该演算法概念是纪录阵列第一位并从其开始遍历,且设立计数器
若遇到和纪录值一样的值计数器+1,不一样的值计数器-1
当计数器为0时,纪录值转为此时遇到的新值
若有个元素佔了阵列一半以上,最后的纪录值便是该元素
总之就是让各不同元素相互抵消最后只留下majority element
在这题实作如下

class Solution:    def majorityElement(self, nums: List[int]) -> int:        ans=0        cnt=0        for i in nums:            if cnt==0:                ans=i            if ans==i:                cnt=cnt+1            else:                cnt=cnt-1        return ans

最后执行时间165ms(faster than 97.56%)

本题学习到的重点:博耶-摩尔多数投票算法（Boyer–Moore majority vote algorithm）
那我们下题见