中位数问题中位数问题

0X00 总结

4. Median of Two Sorted Arrays

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:def findKth(left1, left2, k): if left1 == len(nums1): return nums2[left2 + k - 1] if left2 == len(nums2): return nums1[left1 + k - 1] if k == 1: return min(nums1[left1], nums2[left2]) halfK = k // 2 mid1, mid2 = left1 + halfK - 1, left2 + halfK - 1 if mid1 >= len(nums1): return findKth(left1,mid2+1, k - halfK) elif mid2 >= len(nums2): return findKth(mid1+1, left2, k - halfK)if nums1[mid1] >= nums2[mid2]: return findKth(left1, mid2+1, k - halfK) else: return findKth(mid1+1, left2, k - halfK) sums = len(nums1) + len(nums2) if sums & 1 == 0: # 偶数 return (findKth(0, 0, sums // 2) + findKth(0, 0, sums // 2 + 1)) / 2 else: return findKth(0, 0, sums // 2 + 1)

二分法去做, 每次删除一个列表的元素

295. Find Median from Data Stream

【中位数问题】最大堆与最小堆去做, 保持两个堆之间的流动性

class MedianFinder:def __init__(self): """ initialize your data structure here. """ self.minHeap = [] self.maxHeap = []def addNum(self, num: int) -> None: # 只要涉及插入就必须保持数据在两个堆之间的流动 # 只要我选择 # 长度相等的时候插入最大堆, 长度不等的时候插入最小堆,就能保证两堆不会超过 1 if len(self.minHeap) == len(self.maxHeap): heapq.heappush(self.maxHeap, -heapq.heappushpop(self.minHeap, num)) else: heapq.heappush(self.minHeap, -heapq.heappushpop(self.maxHeap, -num))def findMedian(self) -> float: if len(self.minHeap) == len(self.maxHeap): return (self.minHeap[0] - self.maxHeap[0]) / 2 else: return -self.maxHeap[0]