【算法刷题】堆-数组中第 K 个最大元素

朴灿烈づ我的快乐病毒、 2023-09-30 22:32 17阅读 0赞

## 1. heapq 堆 ##

`Python` 中只有最小堆：

import heapq
    
    a = []
    heapq.heappush(a, 3)  # 添加元素
    heapq.heappush(a, 2)
    heapq.heappush(a, 1)
    while len(a):  # 判断堆的长度
        print(heapq.heappop(a))  # 弹出堆顶元素
    
    # 将列表转换为最小堆
    nums = [2, 3, 1, 4, 5, 6]
    heapq.heapify(nums)
    while len(nums):
        print(heapq.heappop(nums))
    
    # 转换为最大堆
    nums_1 = [2, 3, 1, 4, 5, 6]
    max_heap = []
    for i in max_heap:
        heapq.heappush(max_heap, i * -1)  # 对当前元素乘 -1 ，取出来后再乘以 -1

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

[215. 数组中的第K个最大元素][215. _K]

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    
    请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    
    示例 1:
    
    输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5
    示例 2:
    
    输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    输出: 4
     
    提示：
    
    1 <= k <= nums.length <= 104
    -104 <= nums[i] <= 104

题解一：最小堆变成最大堆

import heapq
    
    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            # 最小堆变为最大堆
            a = list(map(lambda x: x * -1, nums))
            heapq.heapify(a)
            
            r = ""
            while k:
                r = heapq.heappop(a) * -1
                k -= 1
    
            return r

题解二：

import heapq
    
    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            nums.sort()
    
            return nums[-k]

[215. _K]: https://leetcode.cn/problems/kth-largest-element-in-an-array/