头条python后端面试题

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)

考虑极端情况，假设数组大小n足够大，在查找的最后一趟（记为第m趟）才找到，第一趟没找到为O(n)，第二趟没找到为O(n/2)，第m趟没找到为O(n/2m-1)，时间复杂度为O(n(1+1/2+....+1/2m-1))，其中1，1/2，....，1/2m-1为q=1/2的等比数列，则O(n(1+1/2+....+1/2m-1))=O(nC)=O(n)

1+1/2+....+1/2m-1=(1-1/2m)/1-1/2=2-1/2m+1 ~=2

2.python2.x和python3.x的区别

答案：http://www.runoob.com/python/python-2x-3x.html

3.MySQL数据库的底层引擎

链接：https://www.cnblogs.com/wcwen1990/p/6655416.html