hot100 -- 13.堆系列

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

方法1：排序

# 方法1：排序
def FindK(nums, k):nums = sorted(nums, reverse=True)return nums[k-1]

时间复杂度O(nlogn) （排序）

方法2：最小堆（用最小堆维护最大的K个数）

# 方法2：堆（用最小堆维护最大的K个数）
import heapq
def FindK(nums, k):heap = []for num in nums:heapq.heappush(heap, num)if len(heap) > k:heapq.heappop(heap)return heap[0]

时间复杂度O(nlogk)  （遍历n，堆插入和弹出是logk）

方法3：快速选择

# 方法3：快速选择
def FindK(nums, k):# 分区，并确定基准最终位置（左边必然比pos大，右边必然比pos小）def partition(left, right):pivot, pos = right, left                            # 设置基准位置 和 基准的最终位置for i in range(left, right):if nums[i] >= nums[pivot]:                      # 和基准对比，大的从前面开始放nums[i], nums[pos] = nums[pos], nums[i]     # 交换大值，放到前面pos += 1nums[right], nums[pos] = nums[pos], nums[right]     # 放基准元素到它的最终位置return posleft, right = 0, len(nums) - 1while True:pos = partition(left, right)    # 分区if pos == (k-1):                # 对比当前位置 和 目标位置(k-1)return nums[pos]elif pos > (k-1):right = pos - 1else:left = pos + 1

时间复杂度：平均O(n)  ，最坏O(n^2)

2.前 K 个高频元素

问题：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

方法1：哈希表

# 方法1：哈希表 + 排序
import collections
def TopKFreq(nums, k):hash = collections.defaultdict(int)# 统计频率for num in nums:hash[num] += 1freq = sorted(hash.items(), key=lambda x:x[1], reverse=True)    # 直接根据频率对哈希表排序return [num[0] for num in freq[:k]]

方法2：最小堆

# 方法2：最小堆
import heapq
import collections
def TopKFreq(nums, k):hash = collections.defaultdict(int)heap = []# 统计频率for num in nums:hash[num] += 1for num, freq in hash.items():heapq.heappush(heap, [freq, num])       # 最小堆（对首个元素freq筛选）if len(heap) > k:heapq.heappop(heap)return [num[1] for num in heap]