0%

寻找众数

题目:给定一个序列,寻找序列中出现最多的数字,我们称这样的数字为该序列的“众数” 如[2,3,1,1,1]序列的众数为1

法一:一般方法 时间 O(nlog(n)) 空间为不重复的数字数,建立一个二叉排序树,做统计。

法二:时空 O(n)方法:只适合在确定数字的范围时,且范围较小,可以开同样大的数组,遍历一边,一边遍历一边做统计

法一code:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
a = [6, 1, 8, 7, 9, 4, 4, 4, 6, 7,7,6,7,7,7]

class Node:
def __init__(self, data):
self.count = 1
self.data = data
self.lchild = None
self.rchild = None

def search(header, node):

if not header:
header=node
return header
if node.data == header.data:
header.count += 1
if node.data < header.data:
lnode=search(header.lchild, node)
header.lchild=lnode
if node.data > header.data:
rnode=search(header.rchild, node)
header.rchild=rnode
return header
# 建立二叉排序树
def creatTree():
header = Node(a[0])
for i in a[1:]:
node = Node(i)
root=search(header, node)
return header

lists=[]
# 遍历二叉树,求众数
def getModenum(header):
if header:
dict = {'data':0, 'count':1}
dict['data']=header.data
dict['count']=header.count
lists.append(dict)
getModenum(header.lchild)
getModenum(header.rchild)
return lists

if __name__=='__main__':
header=creatTree()
lis=getModenum(header)
modenum = lis[0]
for li in lis:
if(li['count']>modenum['count']):
modenum=li
print('modenum is:')
print(modenum,modenum['data'],modenum['count'])

法二code:

假设数字的范围为1-10,我们先开大小9的数组,然后顺序遍历一次,统计数字个数。

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
a = [6, 1, 8, 7, 9, 4, 4, 4, 6, 7,7,6,7,7,7]
class Array:
def __init__(self,i):
self.index=i
self.count=0
#开了大小9个“数组”
def buildMap():
arrays=[Array(i+1) for i in range(0,10)]
print(arrays)
for i in a:
# print(i)
arrays[i-1].count+=1
return arrays

def getModenum(arrays):
modenum=arrays[0]
for arr in arrays:
print(arr.index,arr.count)
if arr.count>modenum.count:
modenum=arr
print(modenum.index,modenum.count)

if __name__=='__main__':
As=buildMap()
getModenum(As)