Đề 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
-
Chia làm 2 mảng 1 và 2 và thực hiện binary search trên mảng nhỏ hơn
-
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ả:
- 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