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

0%

剑指offer-39数组中出现次数超过一半的数字-python

《剑指offer》python实现系列,全目录

题目描述:

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

第一想法:

建立一个hash表,统计每个数字出现的次数,如果超过了数组长度的一半就return

1
2
3
4
5
6
7
8
9
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
threshold = len(numbers)/2.0
mydict = dict()
for i in numbers:
mydict[i] = mydict.get(i,0)+1
if mydict[i]>threshold:
return i
return 0

剑指offer方法一:排序

如果把这个数组排序,那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。

缺点:改变原数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
if not numbers or len(numbers)<=0:
return 0
numbers.sort()
candidate = numbers[len(numbers)//2]

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

剑指offer方法二:

Boyer-Moore 投票算法

数组中有一个数字出现的次数超过数组长度的一半,即它出现的次数比其他所有数字出现次数的和还要多。因此,我们可以考虑在遍历数组的时候保存两个值:一个是数组中的一个数字作为候选值;另一个是次数。

当我们遍历到下一个数字的时候如果下一个数字和我们之前保存的数字相同,则次数加1:

如果下一个数字和我们之前保存的数字不同,则次数减1.

如果次数为零,那么我们需要保存下一个数字,并把次数设为1.

由于要找的数字出现的次数比其他所有数字出现的次数之和还要多,那么要找的数字肯定是最后设置的数字

注意,如果众数不存在?设置一个检测函数

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

这个之前leetcode做过了,竟然又忘了。

leetcode-169多数元素

if help:小手一抖点个广告 or 大手一挥资助一下