وسيط مصفوفتين مرتبتين

وسيط مصفوفتين مرتبتين

# Examples:
nums1 = [1, 3]
nums2 = [2]
# Combined sorted: [1, 2, 3] → median = 2.0

nums1b = [1, 2]
nums2b = [3, 4]
# Combined sorted: [1, 2, 3, 4] → median = (2+3)/2 = 2.5

print('Example 1 median:', 2.0)
print('Example 2 median:', 2.5)
print('Total length:', len(nums1)+len(nums2), 'and', len(nums1b)+len(nums2b))

نهج الدمج الساذج

def find_median_naive(nums1, nums2):
    # Merge two sorted arrays
    merged = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i]); i += 1
        else:
            merged.append(nums2[j]); j += 1
    merged += nums1[i:] + nums2[j:]
    L = len(merged)
    if L % 2 == 1:
        return float(merged[L // 2])
    return (merged[L//2 - 1] + merged[L//2]) / 2.0

print(find_median_naive([1,3],[2]))    # 2.0
print(find_median_naive([1,2],[3,4]))  # 2.5

فكرة التقسيم

# Partition concept visualised:
# nums1: [1, 3] | [5, 7]   (partition after index 1)
# nums2: [2, 4] | [6, 8]   (partition after index 1)
# Combined left: [1, 3, 2, 4] = 4 elements
# Combined right: [5, 7, 6, 8] = 4 elements
# Valid if max(left) <= min(right): max(3,4)=4 <= min(5,6)=5 ✓
# Median = (max_left + min_right) / 2 = (4+5)/2 = 4.5

nums1, nums2 = [1,3,5,7], [2,4,6,8]
merged = sorted(nums1+nums2)
print('Merged:', merged)
L = len(merged)
print('Median:', (merged[L//2-1]+merged[L//2])/2 if L%2==0 else merged[L//2])

البحث الثنائي عن حد التقسيم

def find_median_sorted_arrays(nums1, nums2):
    # Ensure nums1 is the shorter array
    if len(nums1) > len(nums2):
        return find_median_sorted_arrays(nums2, nums1)
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2    # partition index in nums1
        j = (m + n + 1) // 2 - i  # partition index in nums2
        # Boundary values with sentinels
        max_left1  = float('-inf') if i == 0 else nums1[i-1]
        min_right1 = float('inf')  if i == m else nums1[i]
        max_left2  = float('-inf') if j == 0 else nums2[j-1]
        min_right2 = float('inf')  if j == n else nums2[j]
        if max_left1 <= min_right2 and max_left2 <= min_right1:
            # Found the correct partition
            if (m + n) % 2 == 1:
                return float(max(max_left1, max_left2))
            return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
        elif max_left1 > min_right2:
            hi = i - 1  # i is too large, move left
        else:
            lo = i + 1  # i is too small, move right
    return 0.0

print(find_median_sorted_arrays([1,3],[2]))     # 2.0
print(find_median_sorted_arrays([1,2],[3,4]))   # 2.5

تتبّع البحث الثنائي

def find_median_traced(nums1, nums2):
    if len(nums1) > len(nums2):
        return find_median_traced(nums2, nums1)
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    step = 0
    while lo <= hi:
        step += 1
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        ml1 = float('-inf') if i==0 else nums1[i-1]
        mr1 = float('inf')  if i==m else nums1[i]
        ml2 = float('-inf') if j==0 else nums2[j-1]
        mr2 = float('inf')  if j==n else nums2[j]
        print(f'Step {step}: i={i},j={j}, ml1={ml1},mr1={mr1},ml2={ml2},mr2={mr2}')
        if ml1<=mr2 and ml2<=mr1:
            if (m+n)%2==1: return float(max(ml1,ml2))
            return (max(ml1,ml2)+min(mr1,mr2))/2.0
        elif ml1>mr2: hi=i-1
        else: lo=i+1
    return 0.0

print(find_median_traced([1,3],[2]))

لماذا نبحث ثنائيًا في المصفوفة الأقصر

# Prove j is always valid:
# Total elements in left halves = (m+n+1)//2
# Left from nums1: i elements (0 <= i <= m)
# Left from nums2: j = (m+n+1)//2 - i elements
# j must be in [0, n]:
# j >= 0: i <= (m+n+1)//2 <= (m+n+1)//2 ≤ ... always true for valid lo/hi
# j <= n: i >= (m+n+1)//2 - n = (m-n+1)//2 >= 0 (since m <= n)

m, n = 3, 5  # m <= n
half = (m+n+1)//2
for i in range(m+1):
    j = half - i
    valid = 0 <= j <= n
    print(f'i={i}: j={j}, valid={valid}')

معالجة الأطوال الإجمالية الزوجية والفردية

def median_demo(a, b):
    merged = sorted(a + b)
    L = len(merged)
    expected = merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
    computed = find_median_sorted_arrays(a[:], b[:])
    print(f'a={a}, b={b}: merged={merged}, median={expected}, computed={computed}')
    assert abs(expected - computed) < 1e-9

def find_median_sorted_arrays(nums1, nums2):
    if len(nums1)>len(nums2): return find_median_sorted_arrays(nums2,nums1)
    m,n=len(nums1),len(nums2); lo,hi=0,m
    while lo<=hi:
        i=(lo+hi)//2; j=(m+n+1)//2-i
        ml1=float('-inf') if i==0 else nums1[i-1]; mr1=float('inf') if i==m else nums1[i]
        ml2=float('-inf') if j==0 else nums2[j-1]; mr2=float('inf') if j==n else nums2[j]
        if ml1<=mr2 and ml2<=mr1:
            if (m+n)%2==1: return float(max(ml1,ml2))
            return (max(ml1,ml2)+min(mr1,mr2))/2.0
        elif ml1>mr2: hi=i-1
        else: lo=i+1
    return 0.0

median_demo([1,3],[2])
median_demo([1,2],[3,4])
median_demo([],[1])
median_demo([2],[])  # single array

الحالات الطرفية

def fmsa(a,b):
    if len(a)>len(b): return fmsa(b,a)
    m,n=len(a),len(b); lo,hi=0,m
    while lo<=hi:
        i=(lo+hi)//2; j=(m+n+1)//2-i
        ml1=float('-inf') if i==0 else a[i-1]; mr1=float('inf') if i==m else a[i]
        ml2=float('-inf') if j==0 else b[j-1]; mr2=float('inf') if j==n else b[j]
        if ml1<=mr2 and ml2<=mr1:
            if (m+n)%2==1: return float(max(ml1,ml2))
            return (max(ml1,ml2)+min(mr1,mr2))/2.0
        elif ml1>mr2: hi=i-1
        else: lo=i+1

# Edge cases
print(fmsa([], [1]))             # 1.0
print(fmsa([2], []))             # 2.0
print(fmsa([1,2], [3,4]))        # 2.5
print(fmsa([3,4], [1,2]))        # 2.5
print(fmsa([1,1,1], [1,1]))      # 1.0 (duplicates)
print(fmsa([10,20,30],[5,15,25,35]))  # 17.5

تعميم: العنصر k الأصغر في مصفوفتين

def kth_smallest(nums1, nums2, k):
    if not nums1: return nums2[k-1]
    if not nums2: return nums1[k-1]
    if k == 1: return min(nums1[0], nums2[0])
    # Compare k//2-th elements
    half = k // 2
    i = min(half, len(nums1)) - 1  # index in nums1
    j = min(half, len(nums2)) - 1  # index in nums2
    if nums1[i] <= nums2[j]:
        # Eliminate first (i+1) elements of nums1
        return kth_smallest(nums1[i+1:], nums2, k - (i+1))
    else:
        return kth_smallest(nums1, nums2[j+1:], k - (j+1))

nums1, nums2 = [1,3,5,7], [2,4,6,8]
for k in range(1, 9):
    print(f'k={k}: {kth_smallest(nums1[:], nums2[:], k)}')

مقارنة جميع الأساليب

# Performance comparison
import time, random

def merge_median(a, b):
    merged = sorted(a+b)
    L=len(merged)
    return merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2

def binary_median(a, b):
    if len(a)>len(b): return binary_median(b,a)
    m,n=len(a),len(b);lo,hi=0,m
    while lo<=hi:
        i=(lo+hi)//2;j=(m+n+1)//2-i
        ml1=float('-inf') if i==0 else a[i-1];mr1=float('inf') if i==m else a[i]
        ml2=float('-inf') if j==0 else b[j-1];mr2=float('inf') if j==n else b[j]
        if ml1<=mr2 and ml2<=mr1:
            if (m+n)%2==1: return float(max(ml1,ml2))
            return (max(ml1,ml2)+min(mr1,mr2))/2.0
        elif ml1>mr2: hi=i-1
        else: lo=i+1

for size in [100, 10000]:
    a = sorted(random.sample(range(size*2), size))
    b = sorted(random.sample(range(size*2), size))
    t1=time.time(); [merge_median(a,b) for _ in range(1000)]; t1=time.time()-t1
    t2=time.time(); [binary_median(a,b) for _ in range(1000)]; t2=time.time()-t2
    print(f'n={size}: merge={t1:.4f}s, binary={t2:.4f}s, speedup={t1/t2:.1f}x')

استراتيجية التواصل في المقابلة

# Clean final solution for interviews:
def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        return findMedianSortedArrays(nums2, nums1)
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        max_l1 = nums1[i-1] if i > 0 else float('-inf')
        min_r1 = nums1[i]   if i < m else float('inf')
        max_l2 = nums2[j-1] if j > 0 else float('-inf')
        min_r2 = nums2[j]   if j < n else float('inf')
        if max_l1 <= min_r2 and max_l2 <= min_r1:
            if (m + n) % 2:
                return float(max(max_l1, max_l2))
            return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2.0
        elif max_l1 > min_r2: hi = i - 1
        else: lo = i + 1
# Time: O(log(min(m,n))), Space: O(1)
print(findMedianSortedArrays([1,3],[2]))    # 2.0
print(findMedianSortedArrays([1,2],[3,4]))  # 2.5

اختبار سريع

مراجعة الدرس