中位数问题

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]