2

[每天一道LeetCode] 215. 数组中的第K个最大元素

 2 years ago
source link: https://doumao.cc/index.php/%E7%BC%96%E7%A8%8B/%E6%AF%8F%E5%A4%A9%E4%B8%80%E9%81%93LeetCode-215-%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E7%AC%ACK%E4%B8%AA%E6%9C%80%E5%A4%A7%E5%85%83%E7%B4%A0.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

[每天一道LeetCode] 215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

求第K个最大元素用最小堆，构建一个最多包含K个元素的最小堆，堆顶的元素是堆里K个数字最小的数字。遍历一遍数组，当数字大于堆顶数字时，将堆顶数字出堆，将当前数字入堆。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            if len(heap) < k:
                heapq.heappush(heap, num)
            else:
                if num > heap[0]:
                    heapq.heappop(heap)
                    heapq.heappush(heap, num)
        return heap[0]

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK