算法-topN问题
python1、import numpy as npa = np.array([1,4,3,5,2])b = np.argsort(a)print(b)2、python的内置模块heapq,其原理是基于堆的,也就是二叉树
·
步骤:
第一步:先用Hash表统计每个Query出现的次数,O(N)
第二步: 分治法。可以把所有10亿个数据分组存放
第三步:采用堆数据结构找出Top 10,N*O(logK)
所以,我们最终的时间复杂度是:O(N) + N’*O(logK)
python
- 数组的特点是:寻址容易,插入和删除困难;
- 而链表的特点是:寻址困难,插入和删除容易
- 哈希表既寻址容易,插入删除也容易的数据结构( hash函数选择,针对字符串,整数,排列,具体相应的hash方法)
go
1、
import numpy as np
a = np.array([1,4,3,5,2])
b = np.argsort(a)
print(b)
2、python的内置模块heapq,其原理是基于堆的,也就是二叉树
import heapq
a=[1,2,3,4,5]
re1 = map(a.index, heapq.nlargest(3, a)) #求最大的三个索引 nsmallest与nlargest相反,求最小
re2 = heapq.nlargest(3, a) #求最大的三个元素
print(list(re1)) #因为re1由map()生成的不是list,直接print不出来,添加list()就行了
print(re2)
更多推荐
已为社区贡献2条内容
所有评论(0)