堆71-73

71. 数组中的第K个最大元素class Solution(object): def partition(self, nums, i, j): if i j: key nums[i] while i j: while i j and nums[j] key: j - 1 if i j: nums[i] nums[j] i 1 while i j and nums[i] key: i 1 if i j: nums[j] nums[i] j - 1 nums[i] key return i def findKthLargest(self, nums, k): left, right 0, len(nums) - 1 target len(nums) - k while left right: pivot_idx self.partition(nums, left, right) if pivot_idx target: return nums[pivot_idx] elif pivot_idx target: left pivot_idx 1 else: right pivot_idx - 1class Solution: def minHeapify(self, a, i, heapSize): 向下调整维护最小堆性质 while True: l i * 2 1 r i * 2 2 smallest i if l heapSize and a[l] a[smallest]: smallest l if r heapSize and a[r] a[smallest]: smallest r if smallest i: break a[i], a[smallest] a[smallest], a[i] i smallest def buildMinHeap(self, a, heapSize): 从最后一个非叶子节点开始建堆 for i in range(heapSize // 2 - 1, -1, -1): self.minHeapify(a, i, heapSize) def findKthLargest(self, nums, k): # 取前 k 个元素建小根堆 heap nums[:k] self.buildMinHeap(heap, k) # 遍历剩余元素 for i in range(k, len(nums)): if nums[i] heap[0]: # 只处理比堆顶大的元素 heap[0] nums[i] self.minHeapify(heap, 0, k) return heap[0]72. 前 K 个高频元素给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。class Solution(object): def minHeapify(self, heap, i, heapSize): while True: l i * 2 1 r i * 2 2 smallest i if l heapSize and heap[l][0] heap[smallest][0]: smallest l if r heapSize and heap[r][0] heap[smallest][0]: smallest r if smallest i: break heap[i], heap[smallest] heap[smallest], heap[i] i smallest def buildMinHeap(self, heap, heapSize): for i in range(heapSize // 2 - 1, -1, -1): self.minHeapify(heap, i, heapSize) def topKFrequent(self, nums, k): freq {} for x in nums: freq[x] freq.get(x, 0) 1 items list(freq.items()) heap [(freq, num) for num, freq in items[:k]] self.buildMinHeap(heap, k) for num, f in items[k:]: if f heap[0][0]: heap[0] (f, num) self.minHeapify(heap, 0, k) return [num for _, num in heap]73. 数据流的中位数import heapq class MedianFinder: def __init__(self): self.left [] self.right [] def addNum(self, num): if not self.left or num -self.left[0]: heapq.heappush(self.left, -num) else: heapq.heappush(self.right, num) if len(self.left) len(self.right) 1: moved -heapq.heappop(self.left) heapq.heappush(self.right, moved) elif len(self.right) len(self.left): moved heapq.heappop(self.right) heapq.heappush(self.left, -moved) def findMedian(self) : if len(self.left) len(self.right): return -self.left[0] else: return (-self.left[0] self.right[0]) / 2.0