모든 항목이 고유하고 오름차순으로 정렬된 nums라는 요소 목록이 있다고 가정하면 nums[i] =i가 되도록 최소 i를 찾아야 합니다. 솔루션을 찾을 수 없으면 -1을 반환합니다. 이 문제를 O(log(n)) 시간 안에 풀어야 합니다.
따라서 입력이 nums =[-4, -1, 2, 3, 8]과 같으면 nums[2] =2와 nums[3] =3이지만 2가 더 작기 때문에 출력은 2가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ret :=-1, lhs :=0, rhs :=숫자 크기 - 1
-
동안 lhs <=rhs, 수행
-
mid :=(lhs + rhs) / 2의 바닥
-
nums[mid]가 mid와 같으면
-
ret :=중간
-
-
nums[mid]>=mid이면
-
rhs :=중간 - 1
-
-
그렇지 않으면
-
lhs :=중간 + 1
-
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(nums):
ret = -1
lhs = 0
rhs = len(nums) - 1
while lhs <= rhs:
mid = (lhs + rhs) // 2
if nums[mid] == mid:
ret = mid
if nums[mid] >= mid:
rhs = mid - 1
else:
lhs = mid + 1
return ret
nums = [-4, -1, 2, 3, 8]
print(solve(nums)) 입력
[-4, -1, 2, 3, 8]
출력
2