题目描述

输入 $n$（$1\le n<5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1\le a_i<{10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

n,m=map(int,input().split())
mapp=list(map(int,input().split()))
mapp.sort()
print(mapp[m])

这样子写，超内存认了。但是我用分治思想，也就是快排的变形，写出来还是超内存

def qsort(begin,end):global mapp,mleft = beginright = endvalue_mid=mapp[int((left+right)/2)]while left<=right:while mapp[right] > value_mid:right -= 1while mapp[left] < value_mid:left += 1if left <= right:flag = mapp[left]mapp[left] = mapp[right]mapp[right] = flagleft += 1right -= 1if m<=right:qsort(begin,right)elif left<=m:qsort(left,end)else:print(mapp[right+1])return 0if __name__=="__main__":n, m = map(int, input().split())mapp = list(map(int, input().split()))qsort(0, n - 1)

和快排的思想一样，每一步都把对照参照值，数大的放在右边，数小的放在左边。然后和m进行比较，如果比m大就递归左边的部分，如果小就递归右边的部分。最后数列分成三部分。分别是左边小的，中间一样的，以及右边大的。最后可以得到第m小的数。但是还是超了。不理解了。