题目描述

kth minimum number in a list

算法1

(kth minimum number in a list) $On(log(n))$

Python 代码

n, k = map(int, input().split())
seq = list(map(int, input().split()))

def quick_sort(q, l, r, k):
    if l == r:
        return q[l]
    i, j = l - 1, r + 1
    x = q[(l + r) //2]
    while i < j:
        while True:
            i += 1
            if q[i] >= x:
                break
        while True:
            j -= 1
            if q[j] <= x:
                break
        if i < j: 
            q[i], q[j] = q[j], q[i]
    # length = j - l + 1
    if k <= j:
        return quick_sort(q, l, j, k)
    return quick_sort(q, j + 1, r, k )

quick_sort(seq, 0, n-1, k-1)
print(seq[k-1])