0215. 数组中的第K个最大元素

[giscus[bot]]

0215. 数组中的第K个最大元素

215. 数组中的第K个最大元素 # 标签：数组、分治、快速排序、排序、堆（优先队列） 难度：中等 题目大意 # 描述：给定一个未排序的整数数组 nums 和一个整数 k。

https://algo.itcharge.cn/Solutions/0200-0299/kth-largest-element-in-an-array/

[h-jm98]

快排那个超时了

[X-funbean]

题目要求时间复杂度O(n)，感觉得用桶排序

def findKthLargest(self, nums: List[int], k: int) -> int:
    bucket = [0 for _ in range(20001)]
    for num in nums:
        bucket[num + 10000] += 1

    i = len(bucket) - 1
    while k > 0:
        while bucket[i] == 0:
            i -= 1
        while bucket[i] > 0:
            bucket[i] -= 1
            k -= 1

    return i - 10000