n-1개의 산술 시퀀스 항을 포함하는 nums라는 배열이 있다고 가정합니다. nums의 첫 번째 또는 마지막 요소를 제외한 하나의 요소가 이전에 제거되었습니다. 삭제된 번호를 찾아야 합니다.
따라서 입력이 nums =[5, 7, 11, 13]과 같으면 항목이 공식 2i+5를 따르기 때문에 출력은 9가 됩니다. 따라서 i =2의 경우 2*2 + 5가 됩니다. =9가 누락되었습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
숫자의 크기가 2와 같으면
-
(숫자로 표시된 모든 요소의 합)/2
반환
-
-
nums[0]이 nums[1]과 같으면 /p>
-
숫자 반환[0]
-
-
낮은 :=숫자[0]
-
upper :=숫자의 마지막 요소
-
간격 :=(상단 - 하단)의 바닥 / 숫자의 크기
-
포인터 :=nums 크기의 바닥 / 2
-
왼쪽 :=0
-
오른쪽 :=숫자 크기 - 1
-
왼쪽이 오른쪽과 같지 않은 동안 수행
-
nums[pointer]가 nums[0] + 간격 * 포인터와 같지 않으면
-
nums[pointer - 1]이 nums[0] + interval *(pointer - 1) 과 같으면
-
반환 숫자[0] + 간격 * 포인터
-
-
그렇지 않으면
-
오른쪽 :=포인터
-
포인터 :=바닥(왼쪽 + 오른쪽) / 2
-
-
-
그렇지 않으면
-
오른쪽 - 왼쪽이 1과 같으면
-
포인터 :=오른쪽
-
-
그렇지 않으면
-
왼쪽 :=포인터
-
포인터 :=바닥(왼쪽 + 오른쪽) / 2
-
-
-
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다.
def solve(nums):
if len(nums) == 2:
return sum(nums) // 2
if nums[0] == nums[1]:
return nums[0]
lower = nums[0]
upper = nums[-1]
interval = (upper - lower) // len(nums)
pointer = len(nums) // 2
left = 0
right = len(nums) - 1
while left != right:
if nums[pointer] != nums[0] + interval * pointer:
if nums[pointer - 1] == nums[0] + interval * (pointer -1):
return nums[0] + interval * pointer
else:
right = pointer
pointer = (left + right) // 2
else:
if right - left == 1:
pointer = right
else:
left = pointer
pointer = (left + right) // 2
nums = [5, 7, 11, 13]
print(solve(nums)) 입력
[5, 7, 11, 13]
출력
9