โปรแกรมหาค่าเซ็นเซอร์ที่ตกหล่นจากลิสต์ผิดปกติใน Python

คำอธิบายปัญหา

มีลิสต์ nums1, nums2 หนึ่งลิสต์ถูกต้อง อีกอันผิด: **ลบค่าหนึ่งค่า (ไม่ใช่ค่าสุดท้าย) แล้วเพิ่มค่าผิดท้ายลิสต์** หาค่าที่ถูกลบ (ค่าจริง)

ตัวอย่าง

nums1 = [5, 10, 15], nums2 = [10, 15, 8] → Output: 5

nums1 ถูกต้อง, nums2 ลบ 5 ทิ้ง ใส่ 8 ท้าย

ขั้นตอนการแก้ปัญหา (Binary Search)

1. ลิสต์ทั้งสองเหมือนกันจนถึงจุดที่ลบค่า → หลังจากนั้น nums2 เลื่อนซ้าย 1 ตำแหน่ง
2. Binary search หาจุดแรกที่ nums1[mid] != nums2[mid]
3. ตรวจสอบ: ถ้า nums1[low+1] == nums2[low] → nums1 ถูกต้อง คืน nums1[low] มิฉะนั้น nums2 ถูกต้อง คืน nums2[low]

การตนการทำงาน (Python)

def solve(nums1, nums2):
    low, high = 0, len(nums1) - 1
    while low < high:
        mid = (low + high) // 2
        if nums1[mid] == nums2[mid]:
            low = mid + 1
        else:
            high = mid
    return nums1[low] if nums1[low + 1] == nums2[low] else nums2[low]

nums1 = [5, 10, 15]
nums2 = [10, 15, 8]
print(solve(nums1, nums2))  # Output: 5

อินพุต / เอาต์พุต

Input:  [5, 10, 15], [10, 15, 8]
Output: 5