【深基9.例4】求第 k 小的数#洛谷(MLE)

发布时间:2024年01月15日

题目描述

输入 n n n 1 ≤ n < 5000000 1 \le n < 5000000 1n<5000000 n n n 为奇数)个数字 a i a_i ai? 1 ≤ a i < 10 9 1 \le a_i < {10}^9 1ai?<109),输出这些数字的第 k k k 小的数。最小的数是第 0 0 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,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小的数。但是还是超了。不理解了。

文章来源:https://blog.csdn.net/KLSZM/article/details/135594842
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。