nums라는 숫자 목록이 있고 오름차순으로 정렬되어 있고 또 다른 숫자 대상이 있다고 가정하고 숫자를 정렬된 상태로 유지하려면 대상을 삽입해야 하는 인덱스를 찾아야 합니다. target이 이미 nums에 있는 경우 target을 삽입할 수 있는 가장 큰 인덱스를 반환합니다. 이것을 라이브러리 함수를 사용하지 않고 풀어야 하고 O(log n) 시간 안에 풀어야 합니다.
따라서 입력이 nums =[1,5,6,6,8,9] target =6과 같으면 출력은 4가 됩니다. 6이 이미 있기 때문에 삽입하려면 가능한 가장 큰 인덱스는 4입니다. , 배열은 [1,5,6,6,6,8,9]와 같을 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 왼쪽 :=0
- 맞습니다:=
- 숫자 크기 - 1
- ans :=0
- 왼쪽 <=오른쪽, do
- 중간 :=(왼쪽 + 오른쪽) / 2의 바닥
- 대상>=nums[mid]이면
- ans :=mid + 1
- 왼쪽 :=중간 + 1
- 그렇지 않으면
- 오른쪽 :=중간 - 1
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums, target): left, right = 0, len(nums) - 1 ans = 0 while left <= right: mid = (left + right) // 2 if target >= nums[mid]: ans = mid + 1 left = mid + 1 else: right = mid - 1 return ans nums = [1,5,6,6,8,9] target = 6 print(solve(nums, target))
입력
[1,5,6,6,8,9], 6
출력
4