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

[giscus[bot]]

0215. 数组中的第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