无序数组中线性时间找出第K大的数字，数组线性,#coding:utf8

无序数组中线性时间找出第K大的数字，数组线性,#coding:utf8

#coding:utf8#find KthMaxfrom random import randintdef findKthMax(l,k):    if k>len(l):        return    key=randint(0,len(l)-1)    keyv=l[key]    sl=[i for i in l[:key]+l[key+1:] if i<keyv]    bl=[i for i in l[:key]+l[key+1:] if i>=keyv]    if len(bl)==k-1:        return keyv    elif len(bl)>=k:        return findKthMax(bl,k)    else:        return findKthMax(sl,k-len(bl)-1)if __name__=='__main__':    ll=[1,1,2,2,3,3,4,4,5,5,6,6,7,8,9]    th=findKthMax(ll,3)    print th#该片段来自于http://byrx.net