Giả sử chúng ta có hai danh sách nums1 và nums2, chúng đại diện cho các chỉ số cảm biến. Mỗi danh sách chứa các giá trị duy nhất, do đó a ≠ b. Một trong hai danh sách này đang giữ các chỉ số cảm biến chính xác nhưng danh sách còn lại chứa bị lỗi. Trong danh sách bị lỗi một giá trị, đó không phải là giá trị cuối cùng đã bị loại bỏ và một giá trị sai đã được đặt vào cuối danh sách đó. Chúng tôi phải tìm giá trị thực tế đã bị giảm.
Vì vậy, nếu đầu vào là nums1 =[5, 10, 15] nums2 =[10, 15, 8], thì đầu ra sẽ là 5, vì danh sách đầu tiên nums1 chứa các giá trị thực =[5, 10, 15], trong mảng thứ hai, mảng đó bị bỏ đi và 8 được chèn vào cuối.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- thấp:=0
- cao:=
- kích thước của nums1 - 1
- while low
- giữa:=tầng của (thấp + cao) / 2
- nếu nums1 [mid] giống nums2 [mid] thì
- thấp:=giữa + 1
- nếu không,
- cao:=giữa
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[5, 10, 15], [10, 15, 8]
Đầu ra
5