Đề bài

Cho 2 mảng đã được sắp xếp tăng dần , tìm trung vị (median) của 2 mảng này

Hướng tiếp cận

1. Chia làm 2 mảng 1 và 2 và thực hiện binary search trên mảng nhỏ hơn

2. Dựa trên công thức l1≤r2andl2≤r1 bảo đảm các phần tử nằm bên trái mảng được chọn sẽ nhỏ hơn bên phải. Trong đó:

• l1: Phần tử lớn nhất bên trái mảng 1.
• r1: Phần tử nhỏ nhất bên phải mảng 1.
• l2: Phần tử lớn nhất bên trái mảng 2.
• r2: Phần tử nhỏ nhất bên phải mảng 2. Kết quả:

3. Tính kết quả:

• Nếu tổng số phần tử là lẻ, median là phần tử lớn nhất ở nửa bên trái: max(l1,l2).
• Nếu tổng số phần tử là chẵn, median là trung bình cộng của hai phần tử nằm ở "giữa": max(l1,l2)+min(r1,r2) / 2

Code

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        len1 = len(nums1) # len of arr1
        len2 = len(nums2) # len of arr2
        
        if len1 > len2:
          return self.findMedianSortedArrays(nums2, nums1)
        
        total_len = len1 + len2
        mid = (len1 + len2 + 1) // 2
        low = 0
        high = len1
        
        while low <= high:
          mid1 = (low + high) // 2  # mid index of arr 1
          mid2 = mid - mid1 # mid index of arr 2
          
          l1 = float('-inf')
          l2 = float('-inf')
          r1 = float('inf')
          r2 = float('inf')
          
          if mid1 < len1:
            r1 = nums1[mid1]
          if mid2 < len2:
            r2 = nums2[mid2]
          if mid1 - 1 > -1:
            l1 = nums1[mid1-1]
          if mid2 - 1 > -1:
            l2 = nums2[mid2-1]

          if l1<=r2 and l2<=r1:
            if total_len % 2 == 1:
              return max(l1, l2)
            return (max(l1,l2) + min(r1,r2)) / 2
          elif l1 > r2:
            high=mid1-1
          else:
            low = mid1 + 1
            
        return 0.0