塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-169多数元素

建议看剑指offer 39

https://sbaban.com/jzo39.html


原文:

最初想法:

计算出count,统计每个元素出现的次数,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def majorityElement( nums):
"""
:type nums: List[int]
:rtype: int
"""
mycount = len(nums)//2
templist = {}
for elem in nums:
if elem in templist.keys():
templist[elem] += 1
else:
templist[elem] = 1
for elem,count in templist.items():
if count > mycount:
return elem
改进:边统计边与mycount比较
def majorityElement(self, nums):
if len(nums) == 1:
return nums[0]
mycount = len(nums)//2
templist = {}
for elem in nums:
if elem in templist.keys():
templist[elem] += 1
if templist[elem] > mycount:
return elem
else:
templist[elem] = 1

排序法
先对list做排序,因为众数出现次数大于n//2,

所以当len(list)为奇数时,排好序后,中间位置(n//2)的元素一定是众数。

当len(list)为偶数时,排好序后,中间位置(n//2)的元素一定是众数。

1
2
3
4
5
def majorityElement( nums):
mycount = len(nums)//2
#排序
nums = sorted(nums)
return nums[mycount]

Boyer-Moore 投票算法:
思路:

如果我们把众数记为+1 ,把其他数记为−1 ,将它们全部加起来,因为众数的存在显然和大于 0 ,从结果本身我们可以看出众数比其他数多。

维护一个总分,如果遇到一个我们目前的候选众数,就将计数器加一,否则减一。只要总分等于 0 ,我们就重新选下一个数字当做候选的众数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
if not numbers or len(numbers)<=0:
return 0
threshold = len(numbers)/2.0
candidate, score = 0, 0
for i in numbers:
if score == 0:
candidate = i
score = 1
if i == candidate:
score += 1
else:
score -= 1

return self.check(candidate, numbers)
def check(self,candidate,numbers):
#检测是不是符合结果,防止没有众数的情况出现
mycount = 0
for i in numbers:
if i == candidate:
mycount += 1
if 2*mycount > len(numbers):
return candidate
else:
return 0
if help:小手一抖点个广告 or 大手一挥资助一下