1.给定无序正整数数组,线性时间内找出第K大的值。
from random import randint
def findKthMax(l,k):
if k>len(l):
return
#随机生成一个下标key,并获取下标对应的数组值keyv
key=randint(0,len(l)-1)
keyv=l[key]
#遍历数组(刨除key),sl数组是小于keyv的值,bl数组是大于等于keyv的值
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]
#如果bl的长度恰好是k-1,那么说明keyv就是第k大的数
if len(bl)==k-1:
return keyv
#如果bl的长度大于等于k,说明第k大的数在bl中,迭代findKthMax函数,找出bl中第k大的数
elif len(bl)>=k:
return findKthMax(bl,k)
#如果bl的长度小于k-1,说明第k大的数在sl中,因为bl中已经有len(bl)个比目标值大的数,加上keyv本身,所以要找出sl中第(k-len(bl)-1)大的数
else:
return findKthMax(sl,k-len(bl)-1)
if __name__=='__main__':
ll=[3,4,4,5,5,61,1,2,2,3,3,3,3,6,7,7,7,7,8,9]
th=findKthMax(ll,4)
print(th)
2.python2.x和python3.x的区别
全文:http://www.runoob.com/python/python-2x-3x.html
3.MySQL数据库的底层引擎
链接:https://www.cnblogs.com/wcwen1990/p/6655416.html
面试第一次扑街来的这么快,好想嘤嘤嘤一会儿~
网友评论