App下載

python 怎么在list中找Topk的數(shù)值和索引

猿友 2021-07-26 14:24:36 瀏覽數(shù) (3904)
反饋

在面試中,有些算法問題是比較常問到的,比如今天要介紹的Top K算法。這個算法的需求是,有一個數(shù)組(列表)中有n個數(shù),求其中最大的k個數(shù),這是一種快速排序算法的變種,雖然我們可以直接用排序進行解決,但算法表現(xiàn)并不理想,接下來這篇文章我們就來介紹一下使用二分法進行python求最大的k個數(shù)吧!

需求:

對于一個python list 或者numpy數(shù)組,我需要找到這個list中最大的K個數(shù)及其對應的下標。

解決方式:

1. 可以構造字典通過排序解決,不過代碼量較多。

2. 使用heapq庫,可以直接獲取最大值的下標和數(shù)值。

import heapq
a = [4,2,6,1,9,9]
 
# 獲取下標, 輸出為[4, 5, 2]
heapq.nlargest(3, range(len(a)), a.__getitem__)
 
# 獲取數(shù)值, 輸出為[9, 9, 6]
heapq.nlargest(3,a)

如果要取最小的數(shù),使用 nsmallest即可

Python 利用中間值求TopK 算法

算法思想

首先我們要思考,我要做什么?解決什么問題?

TopK問題,找出一組數(shù)據中的前K個最大值或者最小值,這個數(shù)據是否重復?要做去重處理?

ok 我們明確我們做什么了 ,那介紹的python處理的topK 算法過程是怎么樣的呢?

如果用排序那就沒必要引入topK 了,當數(shù)據強大的時候選取TopK 可以省略很多排序的計算,至于有多優(yōu)化自己去思考下,就比如排列組合的C,A的區(qū)別,一個是抽取,一個是抽取并排列…

以下以找出TopK 的最大值為例,最小值的可以自己修改一下下就可以

介紹的算法思想是利用中間值,將數(shù)列分為三部分 ,

【比中間值大的列表】,中間值,【比中間值小的列表】

那么我們當比較

【比中間值大的列表】的個數(shù) == k

的時候就可以得出前K個最大值了,因此

重點就是找出這個中間值

如何找出中間值

以列表的第一個數(shù)開始為中間值,拆分為三部分

if 【比中間值大的列表】的個數(shù) == k:return 中間值 #程序出口,結束。

if 【比中間值大的列表】的個數(shù) < k :

·····繼續(xù)在【比中間值小的列表】找

·····K - 【比中間值大的列表】的個數(shù) -1 個數(shù)

(為什么要減一,1是前一次的中間值,分的三部分,前部分后部分都沒有包含中間值,因此…)

if 【比中間值大的列表】的個數(shù) > k :

…也就是說比中間值大的列表比K還大,那就在這個列表中繼續(xù)找就行

結合代碼和注釋看

如果要找最小值,只需要改一下就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個數(shù)的情況,
    if k > theBigLen:
        return topKNum(theSmall,k-theBigLen-1)
    # 大值的列表中大于K個數(shù)的情況
    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。


0 人點贊