输入 n n n( 1 ≤ n < 5000000 1 \le n < 5000000 1≤n<5000000 且 n n n 为奇数)个数字 a i a_i ai?( 1 ≤ a i < 10 9 1 \le a_i < {10}^9 1≤ai?<109),输出这些数字的第 k k k 小的数。最小的数是第 0 0 0 小。
请尽量不要使用 nth_element
来写本题,因为本题的重点在于练习分治算法。
5 1
4 3 2 1 5
2
n,m=map(int,input().split())
mapp=list(map(int,input().split()))
mapp.sort()
print(mapp[m])
这样子写,超内存认了。但是我用分治思想,也就是快排的变形,写出来还是超内存
def qsort(begin,end):
global mapp,m
left = begin
right = end
value_mid=mapp[int((left+right)/2)]
while left<=right:
while mapp[right] > value_mid:
right -= 1
while mapp[left] < value_mid:
left += 1
if left <= right:
flag = mapp[left]
mapp[left] = mapp[right]
mapp[right] = flag
left += 1
right -= 1
if m<=right:
qsort(begin,right)
elif left<=m:
qsort(left,end)
else:
print(mapp[right+1])
return 0
if __name__=="__main__":
n, m = map(int, input().split())
mapp = list(map(int, input().split()))
qsort(0, n - 1)
和快排的思想一样,每一步都把对照参照值,数大的放在右边,数小的放在左边。然后和m进行比较,如果比m大就递归左边的部分,如果小就递归右边的部分。最后数列分成三部分。分别是左边小的,中间一样的,以及右边大的。最后可以得到第m小的数。但是还是超了。不理解了。