快速选择

使用了与快速排序类似的算法.
根据与pivot的关系, 将元素分成三类, 三个区间: small, same, big
然后判断k落子哪个区间里面, 然后在哪个区间里面继续查找.

时间复杂度

平均时间复杂度: O(n)

Python 代码

def kth(A, k):
    p = A[len(A)//2]
    small, same, big = [], [], []
    for e in A:
        if e < p:
            small.append(e)
        elif e == p:
            same.append(e)
        else:
            big.append(e)
    if k <= len(small):
        return kth(small, k)
    elif k <= len(small) + len(same):
        return same[0]
    else:
        return kth(big, k - (len(small) + len(same)))



n, k = map(int, input().split())
A = list(map(int, input().split()))
print(kth(A, k))