หาอิลิเมนต์ที่หายไปจากอาร์เรย์ที่ซ้ำกันใน Python

โจทย์: มีอาร์เรย์ 2 ชุด เป็น duplicate ของกัน แต่ชุดหนึ่งขาด 1 อิลิเมนต์ หาตัวที่หาย (อาร์เรย์เรียงลำดับ)

ตัวอย่าง: A=[2,5,6,8,10], B=[5,6,8,10] → หายคือ 2

อัลกอริทึม Binary Search

1. ถ้าตัวแรกต่างกัน → ตัวแรกของอาร์เรย์ยาวกว่าคือคำตอบ
2. Binary search: mid = (low+high)//2
3. ถ้า A[mid] == B[mid] → หายอยู่ขวา (low=mid)
4. มิฉะนั้น → หายอยู่ซ้าย (high=mid)
5. จน low == high-1 → คำตอบคือ A[high]

ตัวอย่างโค้ด

def solve(A, B, N):
    if N == 1:
        return A[0]
    if A[0] != B[0]:
        return A[0]
    low, high = 0, N - 1
    while low < high:
        mid = (low + high) // 2
        if A[mid] == B[mid]:
            low = mid
        else:
            high = mid
        if low == high - 1:
            break
    return A[high]

def get_missing_element(A, B):
    M, N = len(A), len(B)
    if N == M - 1:
        return solve(A, B, M)
    elif M == N - 1:
        return solve(B, A, N)
    return "Not found"

print(get_missing_element([2,5,6,8,10], [5,6,8,10]))  # 2

ผลลัพธ์

2

สรุป: Binary Search บนอาร์เรย์เรียงลำดับ O(log n) time เปรียบเทียบค่าที่ index เดียวกัน หาจุดที่เริ่มต่างกัน