python 怎么在list中找Topk的数值和索引
- 后端
- 猿友
- 0
在面试中，有些算法问题是比较常问到的，比如今天要介绍的Top K算法。这个算法的需求是，有一个数组（列表）中有n个数，求其中最大的k个数，这是一种快速排序算法的变种，虽然我们可以直接用排序进行解决，但算法表现并不理想，接下来这篇文章我们就来介绍一下使用二分法进行python求最大的k个数吧！
需求：
对于一个python list 或者numpy数组，我需要找到这个list中最大的K个数及其对应的下标。
解决方式：
1. 可以构造字典通过排序解决，不过代码量较多。
2. 使用heapq库，可以直接获取最大值的下标和数值。
import heapq
a = [4,2,6,1,9,9]
# 获取下标， 输出为[4, 5, 2]
heapq.nlargest(3, range(len(a)), a.__getitem__)
# 获取数值， 输出为[9, 9, 6]
heapq.nlargest(3,a)如果要取最小的数，使用 nsmallest即可
Python 利用中间值求TopK 算法
算法思想
首先我们要思考，我要做什么？解决什么问题？
TopK问题，找出一组数据中的前K个最大值或者最小值，这个数据是否重复？要做去重处理？
ok 我们明确我们做什么了 ，那介绍的python处理的topK 算法过程是怎么样的呢？
如果用排序那就没必要引入topK 了，当数据强大的时候选取TopK 可以省略很多排序的计算，至于有多优化自己去思考下，就比如排列组合的C，A的区别，一个是抽取，一个是抽取并排列…
以下以找出TopK 的最大值为例，最小值的可以自己修改一下下就可以
介绍的算法思想是利用中间值，将数列分为三部分 ，
【比中间值大的列表】，中间值，【比中间值小的列表】
那么我们当比较
【比中间值大的列表】的个数 == k
的时候就可以得出前K个最大值了，因此
重点就是找出这个中间值
如何找出中间值
以列表的第一个数开始为中间值，拆分为三部分
if 【比中间值大的列表】的个数 == k：return 中间值 #程序出口，结束。
if 【比中间值大的列表】的个数 < k ：
·····继续在【比中间值小的列表】找
·····K - 【比中间值大的列表】的个数 -1 个数
（为什么要减一，1是前一次的中间值，分的三部分，前部分后部分都没有包含中间值，因此…）
if 【比中间值大的列表】的个数 > k ：
…也就是说比中间值大的列表比K还大，那就在这个列表中继续找就行
结合代码和注释看
如果要找最小值，只需要改一下就ok ,还可以设置一个布尔值的输入，来做前K个最大值最小值
#2019 11 04
#author 半斤地瓜烧
#TopK 算法，找出序列中前K个最大值的
#输入一个seq
# 输出以seq[0]为中间值 划分的三个部分，中间值，比这个值大的seq ,比这个值小的seq，
# 即splitNum,theBig,theSmall
def Split_Seq(seq):
splitNum = seq[0]
seq = seq[1:]#两个部分都不包含中间值，因此切片去除seq[0]
theBig = [x for x in seq if x >= splitNum]
theSmall = [x for x in seq if x < splitNum]
return splitNum,theBig,theSmall
#找出中间值
def topKNum(seq,k):
splitNum, theBig, theSmall = Split_Seq(seq)
theBigLen = len(theBig)
if k == theBigLen:
return splitNum#出口,返回这个中间值,
# 为什么不直接返回thebig?因为存在递归的原因thebig 不是在初始的seq找出来的
#需要重新Split,即可，读者自己思考
# 大值的列表中还未够K个数的情况，
if k > theBigLen:
return topKNum(theSmall,k-theBigLen-1)
# 大值的列表中大于K个数的情况
return topKNum(theBig,k)
#由中间值找出TopK个值，<list>
def getTopK(seq,k):
return [i for i in seq if i > topKNum(seq, k)]
if __name__ == '__main__':
alist = [7, 3, 5, 1,885,234,2211,222,22, 2, 11, 2, 115]
print("===为了验证，引入排序观看===", sorted(alist,reverse= True))
print(getTopK(alist, 3))以上就是TopK算法的全部介绍了，希望能给大家一个参考，也希望大家多多支持W3Cschool。
免责申明：本站发布的内容（图片、视频和文字）以转载和分享为主，文章观点不代表本站立场，如涉及侵权请联系站长邮箱：xbc-online@qq.com进行反馈，一经查实，将立刻删除涉嫌侵权内容。
