AcWing 786. 第k个数
原题链接
简单
作者:
Paradoggy
,
2023-10-01 11:43:49
,
所有人可见
,
阅读 60
思路
将k值当做物理地址的值,比如第5个数其实就是数组4的位置,第2个数就是数组1的位置
每次只需要判断k在左区间还是右区间,一直递归查找k所在区间
最后只剩一个数时,只会有数组[k]一个数,返回数组[k]的值就是答案
n, k = map(int,input().split())
A = list(map(int,input().split()))
def quickSort(l, r, k):
if l >= r:
return A[k]
x = A[l]
i, j = l-1, r+1
while i < j:
i += 1
while A[i] < x:
i += 1
j -= 1
while A[j] > x:
j -= 1
if i < j:
A[i], A[j] = A[j], A[i]
if k <= j:
return quickSort(l, j, k)
else:
return quickSort(j+1, r, k)
print(quickSort(0, n-1, k-1))