Chương trình Python tìm giá trị cảm biến bị loại khỏi danh sách lỗi

Cho hai danh sách nums1, nums2 (giá trị duy nhất). Một danh sách chính xác, một danh sách lỗi: bị thiếu 1 giá trị (không phải giá trị cuối) và thêm 1 giá trị sai vào cuối. Tìm giá trị bị thiếu.

Ví dụ

Input: nums1 = [5, 10, 15], nums2 = [10, 15, 8]

Output: 5

Giải thích: nums1 chính xác. nums2 thiếu 5 và thêm 8 vào cuối.

Thuật toán (Binary Search)

Vì cả hai mảng ban đầu giống nhau (trừ phần tử bị thay), ta so sánh từng cặp phần tử cùng chỉ số bằng binary search:

1. low = 0, high = len(nums1) - 1.
2. Khi low < high:
   • mid = (low + high) // 2
   • Nếu nums1[mid] == nums2[mid] → phần tử khác ở bên phải: low = mid + 1
   • Ngược lại → phần tử khác ở bên trái hoặc tại mid: high = mid
3. Kết thúc: low là chỉ số đầu tiên khác nhau.
   • Nếu nums1[low+1] == nums2[low] → nums1[low] là giá trị bị thiếu.
   • Ngược lại → nums2[low] là giá trị bị thiếu (trường hợp nums2 là mảng chính xác).

Mã nguồn 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]

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

Độ phức tạp

• Thời gian: O(log n)
• Không gian: O(1)

Lưu ý: Yêu cầu cả hai mảng có cùng độ dài và chỉ khác nhau ở đúng một vị trí (phần tử bị bỏ + phần tử sai ở cuối).