센서 메트릭을 나타내는 두 개의 목록 nums1과 nums2가 있다고 가정합니다. 각 목록은 고유한 값을 포함하므로 ≠ b. 이 두 목록 중 하나는 정확한 센서 메트릭을 보유하고 있지만 다른 하나는 결함을 포함하고 있습니다. 잘못된 목록에서 마지막 값이 아닌 하나의 값이 삭제되고 해당 목록의 끝에 잘못된 값이 배치되었습니다. 떨어졌던 실제 값을 찾아야 합니다.
따라서 입력이 nums1 =[5, 10, 15] nums2 =[10, 15, 8]과 같으면 첫 번째 목록 nums1이 실제 값 =[5, 10, 15]를 보유하므로 출력은 5가 됩니다. 두 번째 배열에서는 삭제되고 끝에 8이 삽입됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 낮음 :=0
- 높음 :=
- nums1 - 1의 크기
- 낮은 동안 <높은, do
- 중간 :=(낮음 + 높음) / 2의 바닥
- nums1[mid]이 nums2[mid]와 같으면
- 낮음 :=중간 + 1
- 그렇지 않으면
- 높음 :=중간
- nums1[low + 1]이 nums2[low]와 같으면 nums1[low]를 반환하고 그렇지 않으면 nums2[low]를 반환합니다.
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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))
입력
[5, 10, 15], [10, 15, 8]
출력
5