XY

没有任何借口
posts - 9, comments - 31, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

算法:找出n个数中重复最多的10个数

Posted on 2017-09-29 22:20 路缘 阅读(1367) 评论(0)  编辑 收藏 引用 所属分类: C/C++

题目很清晰,直接上python代码。下面的解法是假设内存足够存储n个数的字典。如果内存不够,我想的解法在时间复杂度上不太理想。
如果内存不够,我想到的解法是在下面解法的基础上,对dictCounts存储数量设定阈值,删除出现次数较少的数对应的项,且要确保删除该数在后续数列中不再出现或出现的次数加上其总次数仍然较少。
这就让数据的遍历增加了不少。网上也有很多类似该题的问题并给出了解法,有的给出把数分为很多组,再对每组数找出最多的10个数,然后对找出的结果进行归并,
我认为其是有漏洞的,如果某个数在所有分组中并不占优,而都有出现,其就有可能被漏选掉。

这个题是我面试时碰到的,当时想得过于复杂,还自己给自己挖坑,问数据量会不会很大,考官说了会很大,几百万,其实即使几百万对内存来讲也不是什么问题,又不是几千亿
,当时勉强给了个解法还有很多纰漏,自己虽然编程多年,这方面的训练还是不够。写下来反思。

 1 import pandas as pd
 2 import copy
 3 
 4 class BenchMark:
 5     def __init__(self):
 6         self.MIN = 10000
 7         self.data = 0
 8     def Reset(self):
 9         self.MIN = 10000
10         self.data = 0
11 
12 dictCounts = {}
13 dictTop10_D2C = {}
14 BENCH_MARK = BenchMark()
15 LAST_BENCH_MARK = BenchMark()
16 run_count1 = 0
17 run_count2 = 0
18 
19 def FindTop10(data):
20     global BENCH_MARK, LAST_BENCH_MARK,run_count1,run_count2
21     if(data in dictCounts):
22         dictCounts[data] += 1
23     else:
24         dictCounts[data] = 1
25 
26     temp = dictCounts[data]
27     
28     #just record run times
29     run_count1 += 1
30     
31     if LAST_BENCH_MARK.MIN != 10000 and temp< LAST_BENCH_MARK.MIN:
32         return
33 
34     dictTop10_D2C[data] = temp
35 
36     if len(dictTop10_D2C)>10:
37         BENCH_MARK.Reset()
38         for item in dictTop10_D2C:
39             
40             #just record run times
41             run_count2+=1
42             
43             if dictTop10_D2C[item] < BENCH_MARK.MIN:
44                 BENCH_MARK.MIN = dictTop10_D2C[item]
45                 BENCH_MARK.data = item
46         LAST_BENCH_MARK = copy.deepcopy(BENCH_MARK)
47         dictTop10_D2C.pop(BENCH_MARK.data)
48 
49 def PrintData2Count(aDict):
50     for key in aDict:
51         print('%.1f:%d' % (key, aDict[key]))
52 
53 if __name__ == '__main__':
54     df = pd.read_csv('D:/data/ctp_data/rb/201709/rb1801_20170905.csv')
55     for data in df['LastPx']:
56         FindTop10(data)
57 
58     PrintData2Count(dictCounts)
59     print("==============dictCounts length:", len(dictCounts))
60     PrintData2Count(dictTop10_D2C)
61 
62     print("run_count1:%d,run_count2:%d" %(run_count1,run_count2))
63 

运行结果如下:

。。。。。。

4121.0:206
4123.0:278
4124.0:180
4122.0:244
4125.0:118
4126.0:34
4127.0:4
4081.0:1366
4080.0:1073
4077.0:1072
4078.0:1091
4079.0:800
4076.0:874
4075.0:886
4074.0:1108
4071.0:719
4073.0:1281
4072.0:1049
4070.0:567
4069.0:442
4068.0:290
4067.0:199
4066.0:204
4065.0:109
4064.0:60
4063.0:80
4062.0:57
4061.0:70
4060.0:70
4059.0:32
4057.0:6
4058.0:22
4129.0:6
4137.0:2
4135.0:2
4133.0:2
==============dictCounts length: 75
4109.0:2080
4108.0:2047
4095.0:3009
4096.0:2785
4094.0:2265
4099.0:2573
4098.0:2702
4097.0:2491
4100.0:2147
4107.0:1809
run_count1:70684,run_count2:19679


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理