Persediaan Temu Duga Pengaturcaraan · Pelajaran

Median Dua Tatasusunan Terisih

Selesaikan masalah median dua tatasusunan terisih dalam O(log(min(m,n))) menggunakan carian binari pada sempadan pembahagian tatasusunan yang lebih pendek.

Pelajaran 4 daripada 413 langkah

Median Dua Tatasusunan Terisih ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Median Dua Tatasusunan Terisih

Median Dua Tatasusunan Terisih (LeetCode 4) ialah masalah sukar klasik. Diberikan dua tatasusunan terisih nums1 (panjang m) dan nums2 (panjang n), cari median jujukan terisih gabungannya dalam masa O(log(min(m,n))). Pendekatan naif menggabungkan kedua-dua tatasusunan dalam O(m+n), tetapi penyelesaian optimum menggunakan carian binari pada sempadan pembahagian. Ini merupakan salah satu masalah sukar yang paling kerap ditanya oleh syarikat teknologi terkemuka.

# 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))

Pendekatan Cantuman Naif

Pendekatan O(m+n) yang paling mudah: cantumkan kedua-dua tatasusunan terisih, kemudian cari median. Mencantumkan dua tatasusunan terisih mengambil masa O(m+n). Median bagi tatasusunan sepanjang L ialah arr[L//2] jika L ganjil, atau (arr[L//2-1] + arr[L//2]) / 2 jika L genap. Kaedah ini betul tetapi tidak memenuhi keperluan O(log(min(m,n))). Dalam temu duga, sentiasa bentangkan pendekatan ini dahulu untuk menetapkan titik asas, kemudian optimumkan penyelesaian.

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

Idea Pembahagian

Pemerhatian utama: median membahagikan tatasusunan gabungan kepada dua bahagian yang sama besar. Kita perlu mencari satu pembahagian bagi nums1 dan satu pembahagian bagi nums2 supaya: (1) Jumlah saiz bahagian kiri sama dengan jumlah saiz bahagian kanan. (2) Semua unsur dalam bahagian kiri ≤ semua unsur dalam bahagian kanan. Jika kita melakukan carian binari untuk titik pembahagian yang betul dalam nums1, pembahagian dalam nums2 ditentukan secara automatik berdasarkan kekangan jumlah panjang.

# 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])

Carian Binari pada Pembahagian

Lakukan carian binari pada indeks pembahagian i bagi nums1 (tatasusunan yang lebih pendek). Indeks pembahagian j dalam nums2 ditentukan sebagai j = (m+n+1)//2 - i (memastikan bahagian kiri mempunyai (m+n+1)//2 unsur). Pembahagian itu sah apabila nums1[i-1] ≤ nums2[j] dan nums2[j-1] ≤ nums1[i]. Carian binari melaraskan i ke atas atau ke bawah untuk mencari keseimbangan ini.

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

Menjejaki Carian Binari

Jejaki nums1=[1,3], nums2=[2]: m=2, n=1, jumlah=3, lo=0, hi=2. i=(0+2)//2=1, j=(2+1+1)//2-1=1. max_left1=nums1[0]=1, min_right1=nums1[1]=3, max_left2=nums2[0]=2, min_right2=inf (j=1=n). Semak: 1≤inf dan 2≤3 ✓. Jumlah ganjil: pulangkan max(1,2)=2.0. ✓ Algoritma menemui pembahagian pada langkah pertama kerana saiz tatasusunan adalah kecil.

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]))

Mengapa Carian Binari pada Tatasusunan yang Lebih Pendek

Kita melakukan carian binari pada tatasusunan yang lebih pendek untuk mencapai O(log(min(m,n)), bukannya O(log(m+n)). Pembahagian tatasusunan yang lebih panjang ditentukan sepenuhnya oleh pembahagian tatasusunan yang lebih pendek. Menukar input jika len(nums1) > len(nums2) memastikan tatasusunan yang lebih pendek sentiasa menjadi ruang carian. Invarian: apabila j diperoleh daripada i dan jumlah panjang, j sentiasa merupakan indeks pembahagian yang sah untuk nums2.

# 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}')

Mengendalikan Panjang Jumlah Genap dan Ganjil

Apabila panjang gabungan ganjil: median ialah nilai maksimum bahagian kiri (max(max_left1, max_left2)). Apabila genap: median ialah purata nilai maksimum bahagian kiri dan nilai minimum bahagian kanan. Formula (m+n+1)//2 untuk saiz bahagian kiri berfungsi bagi kedua-duanya: bagi jumlah genap, ia memberikan n//2 (satu unsur tambahan di sebelah kiri), kemudian kita mengambil purata dengan min_right untuk mendapatkan median genap.

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

Kes Pinggir

Kes pinggir yang kritikal: (1) Satu tatasusunan kosong — median tatasusunan yang tidak kosong. (2) Semua unsur dalam satu tatasusunan lebih kecil daripada tatasusunan yang satu lagi — pembahagian berada pada salah satu hujung. (3) Unsur pendua — algoritma mengendalikannya secara semula jadi. (4) Kedua-dua tatasusunan mempunyai panjang 1 — median mudah bagi dua unsur. Sentiasa uji kes-kes ini selepas menulis kod. Nilai penanda -∞ dan +∞ mengendalikan pembahagian sempadan (i=0 atau i=m) dengan kemas.

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

Pengitlakan: Unsur Ke-k Terkecil dalam Dua Tatasusunan

Masalah median boleh digeneralisasikan kepada pencarian unsur ke-k terkecil merentas dua tatasusunan terisih. Pada setiap langkah, bandingkan unsur ke-k//2 bagi setiap tatasusunan. Singkirkan separuh yang lebih kecil: k//2 unsur tersebut semuanya lebih kecil daripada unsur ke-k, jadi kita boleh membuangnya. Kurangkan k sebanyak k//2 dan lakukan panggilan rekursif. Kes asas: satu tatasusunan kosong (pulangkan unsur ke-k daripada tatasusunan yang berbaki), atau k=1 (pulangkan nilai minimum daripada kedua-dua unsur hadapan). Masa: O(log k) = O(log(m+n)).

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)}')

Membandingkan Semua Pendekatan

Perbandingan akhir: Gabungan tatasusunan: O(m+n) time, ruang O(m+n). Carian binari pada pembahagian: O(log(min(m,n))) time, ruang O(1). Rekursi elemen terkecil ke-k: O(log(m+n)) time, tindanan panggilan O(log k). Kaedah pembahagian carian binari ialah kaedah yang dijangka oleh penemu duga untuk masalah ini. Ini ialah masalah LeetCode umum yang paling sukar untuk diterangkan dengan jelas — berlatihlah logik pembahagian dan empat semakan sempadan sehingga semuanya menjadi automatik.

# 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')

Strategi Komunikasi Temu Duga

Untuk masalah sukar ini dalam temu duga: (1) Nyatakan pendekatan naif penggabungan O(m+n) dengan segera — ini menunjukkan kecekapan. (2) Terangkan matlamat O(log(min(m,n))) dan idea pembahagian. (3) Huraikan invarian pembahagian: max_left1 ≤ min_right2 serta max_left2 ≤ min_right1. (4) Kendalikan nilai penanda secara jelas. (5) Nyatakan formula median untuk kes ganjil/genap. (6) Uji dengan 1-2 contoh. Rangka kerja 5 langkah ini menunjukkan penyelesaian masalah secara sistematik walaupun bagi masalah yang jarang dapat diselesaikan dengan sempurna oleh calon di bawah tekanan.

# 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

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Imbas Kembali Pelajaran

Dalam pelajaran ini anda telah mempelajari: median dua tatasusunan tersusun boleh dicari dalam O(log(min(m,n))) dengan melakukan carian binari untuk mencari sempadan pembahagian yang betul dalam tatasusunan yang lebih pendek, pembahagian adalah sah apabila max_left1 ≤ min_right2 serta max_left2 ≤ min_right1, dengan nilai penanda mengendalikan kes sempadan, dan generalisasi elemen terkecil ke-k menggunakan pendekatan penyingkiran separuh secara rekursif dalam O(log k) time. Tahniah kerana telah menamatkan pelajaran Bahagi dan Takluk — kini anda mempunyai kit alat komprehensif untuk temu duga pengekodan!

Percuma untuk bermula

Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 90
Pelajaran: 360

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Median Dua Tatasusunan Terisih” percuma?

Ya — teks penuh “Median Dua Tatasusunan Terisih” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Median Dua Tatasusunan Terisih”?

Selesaikan masalah median dua tatasusunan terisih dalam O(log(min(m,n))) menggunakan carian binari pada sempadan pembahagian tatasusunan yang lebih pendek. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.

Berapa lamakah pelajaran “Median Dua Tatasusunan Terisih” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?

Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Templat Bahagi dan Takluk
Mengira Penyongsangan Menggunakan Isihan Gabung Terubah Suai
Unsur Majoriti: Pengundian Boyer-Moore
Median Dua Tatasusunan Terisih

← Kembali ke Persediaan Temu Duga Pengaturcaraan