LeetCode 4 Median of Two Sorted Arrays: แบ่งสองฝั่งให้ซ้ายไม่เกินขวา

โจทย์ Median of Two Sorted Arrays ให้ array เรียงสองชุดและต้องหามัธยฐานของข้อมูลรวม โดย constraint ต้องการเวลาเชิงลอการิทึม ความยากคือหาตำแหน่งกลางโดยไม่ merge ทุกสมาชิกครับ

สรุปโจทย์ด้วยคำของเรา

เราต้องแบ่งข้อมูลรวมเป็นครึ่งซ้ายและครึ่งขวาให้จำนวนสมาชิกสมดุล และค่าสูงสุดฝั่งซ้ายไม่เกินค่าต่ำสุดฝั่งขวา ถ้าจำนวนรวมเป็นคี่ คำตอบคือหัวของครึ่งขวาหรือท้ายของครึ่งซ้ายตามนิยาม partition; ถ้าเป็นคู่ให้เฉลี่ยสองค่ากลาง

วิธีที่ 1: merge จนถึงกลาง

ใช้ pointer สองตัวแบบ merge sort แล้วหยุดเมื่อถึงตำแหน่งกลาง ไม่จำเป็นต้องสร้าง list ทั้งก้อน

• เวลา O(m + n) ในกรณีแย่สุด
• หน่วยความจำเพิ่ม O(1)
• อ่านง่ายและเหมาะเป็น oracle ใน test แต่ไม่ผ่านเป้าหมาย logarithmic ของโจทย์

วิธีที่ 2: ตัด k-th ทีละครึ่ง

นิยามฟังก์ชันหาอันดับที่ k แล้วตัด prefix ของ array ที่มีค่าจุดตรวจเล็กกว่า ทำซ้ำจน k เหลือหนึ่ง

• เวลา O(log(m + n))
• หน่วยความจำ O(1) ถ้าเขียน iterative
• generalize ไปหา percentile ได้ แต่ index arithmetic มีหลายจุดให้พลาด

วิธีที่ 3: binary partition บน array ที่สั้นกว่า

เดาตำแหน่งตัดใน array สั้น แล้วคำนวณจุดตัดของอีก array ให้ครึ่งซ้ายมีจำนวนตามต้องการ ถ้า leftA > rightB ขยับซ้าย ถ้า leftB > rightA ขยับขวา เมื่อทั้งสองเงื่อนไขผ่าน เราพบ partition กลาง

• เวลา O(log(min(m, n)))
• หน่วยความจำเพิ่ม O(1)
• เป็น best default ตาม constraint แต่ต้องจัด sentinel และ array ว่างให้ครบ

import unittest


def median_merge(a, b):
    total = len(a) + len(b)
    target = total // 2
    i = j = 0
    previous = current = 0
    for _ in range(target + 1):
        previous = current
        if j >= len(b) or (i < len(a) and a[i] <= b[j]):
            current = a[i]
            i += 1
        else:
            current = b[j]
            j += 1
    return float(current) if total % 2 else (previous + current) / 2


def median_partition(a, b):
    if len(a) > len(b):
        a, b = b, a
    total = len(a) + len(b)
    half = (total + 1) // 2
    low, high = 0, len(a)

    while low <= high:
        cut_a = (low + high) // 2
        cut_b = half - cut_a
        left_a = float("-inf") if cut_a == 0 else a[cut_a - 1]
        right_a = float("inf") if cut_a == len(a) else a[cut_a]
        left_b = float("-inf") if cut_b == 0 else b[cut_b - 1]
        right_b = float("inf") if cut_b == len(b) else b[cut_b]

        if left_a <= right_b and left_b <= right_a:
            if total % 2:
                return float(max(left_a, left_b))
            return (max(left_a, left_b) + min(right_a, right_b)) / 2
        if left_a > right_b:
            high = cut_a - 1
        else:
            low = cut_a + 1
    raise ValueError("inputs must be sorted and not both empty")


class MedianTests(unittest.TestCase):
    def check(self, a, b, expected):
        self.assertEqual(median_merge(a, b), expected)
        self.assertEqual(median_partition(a, b), expected)

    def test_odd_and_even(self):
        self.check([1, 3], [2], 2.0)
        self.check([1, 2], [3, 4], 2.5)

    def test_empty_duplicates_and_unbalanced(self):
        self.check([], [5], 5.0)
        self.check([1, 1], [1, 1], 1.0)
        self.check([1], [2, 3, 4, 5, 6], 3.5)


if __name__ == "__main__":
    unittest.main()

Decision table

สถานการณ์	Merge ถึงกลาง	K-th elimination	Binary partition
input เล็ก	อ่านง่ายที่สุด	เกินจำเป็น	ใช้ได้
input ใหญ่มาก	ช้าตามจำนวนสมาชิก	ดี	ดีที่สุด
memory จำกัด	O(1) หากไม่สร้าง list	O(1)	O(1)
readability สำคัญ	ดี	ปานกลาง	ต้องอธิบาย invariant
input เป็น stream เรียง	ใช้ได้และหยุดกลาง	ต้อง random access	ต้อง random access
ห้ามแก้ input	ผ่าน	ผ่าน	ผ่าน
input ยังไม่เรียง	ต้อง sort ก่อน	ใช้ไม่ได้ตรง ๆ	ใช้ไม่ได้ตรง ๆ

Best default: binary partition บน array สั้นกว่า เพราะตรง constraint O(log(min(m,n))) และไม่สร้างข้อมูลรวม

Edge cases

• array หนึ่งว่าง แต่อีก array ต้องไม่ว่าง
• จำนวนรวมเป็นคู่กับคี่
• ค่าซ้ำ, ค่าติดลบ และขนาดต่างกันมาก
• จุดตัดอยู่ก่อนสมาชิกแรกหรือหลังสมาชิกสุดท้าย จึงต้องมี sentinel
• input ไม่เรียงทำให้ invariant พัง ควรถือเป็น precondition ไม่ตรวจด้วย scan เพราะจะทำลาย complexity

Recap

• แบ่งครึ่งซ้ายให้มี (m+n+1)//2 สมาชิก
• search บน array ที่สั้นกว่า
• partition ถูกเมื่อ leftA <= rightB และ leftB <= rightA
• ใช้ merge เป็น oracle ใน test และ partition เป็นคำตอบหลัก