摘要
Title: 786. 第k个数
Tag: 快速选择
Memory Limit: 64 MB
Time Limit: 1000 ms

786. 第k个数

题意

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
思路

快速选择算法，时间复杂度为 $O(2n)$ （因确定往一边递归，所以可以去掉一个log），思路基本与快排类似

代码

带注释版

'''
Author: NEFU AB-IN
Date: 2022-02-16 16:15:05
FilePath: \ACM\Acwing\786.py
LastEditTime: 2022-02-16 16:19:42
'''

a = []


def quickselect(l, r, k):
    if l >= r:
        return a[l]
    pivot = a[l + r >> 1]
    i, j = l - 1, r + 1
    while i < j:
        while True:
            i += 1
            if a[i] >= pivot:
                break
        while True:
            j -= 1
            if a[j] <= pivot:
                break
        if i < j:
            a[i], a[j] = a[j], a[i]
    # 前面基本与快排相同
    sl = j - l + 1 #左半边区间的数
    if k <= sl: #如果k在左半边，那么递归左边
        return quickselect(l, j, k)
    else: #否则递归右边，找第k-sl的数
        return quickselect(j + 1, r, k - sl)


if __name__ == "__main__":
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    print(quickselect(0, n - 1, k))

无注释版

'''
Author: NEFU AB-IN
Date: 2022-02-16 16:15:05
FilePath: \ACM\Acwing\786.py
LastEditTime: 2022-02-16 16:19:42
'''

a = []


def quickselect(l, r, k):
    if l >= r:
        return a[l]
    pivot = a[l + r >> 1]
    i, j = l - 1, r + 1
    while i < j:
        while True:
            i += 1
            if a[i] >= pivot:
                break
        while True:
            j -= 1
            if a[j] <= pivot:
                break
        if i < j:
            a[i], a[j] = a[j], a[i]
    sl = j - l + 1
    if k <= sl:
        return quickselect(l, j, k)
    else:
        return quickselect(j + 1, r, k - sl)


if __name__ == "__main__":
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    print(quickselect(0, n - 1, k))

786. 第k个数

题意

思路

代码