log 2022-05-24
blog
study
leet study
https://leetcode.com/problems/search-in-rotated-sorted-array/
문제 이해가 잘 안된다. [0,1,2,4,5,6,7]
rotated at pivot index 3 and become [4,5,6,7,0,1,2].
아 잠만, 그냥 한번 읽으면 되지 않나 했는데, 시간복잡도가 O(lgN)이어야 한다고 한다. 그러려면 한번 쭉 읽는것조차 허용되지 않는다.
일단, 이분탐색이든 값 이용이든 해야 한다.
그런데, 이분탐색하려면 정렬되어 있어야 하는데, 웬만큼 정렬되어 있긴한데 피봇이 가운데 있어서 애매하다. 이 수열을 두 번 붙이면 가운데에 정렬된 원본 수열이 있겠지만, 어디부터 시작이고 끝인지 찾기가 애매하다.
값-인덱스 기법은 어떨까
[4,5,6,7,0,1,2] [4,5,6,7,0,1,2]
삼분탐색을 써야 하나 싶기도 한데.. 엣지케이스 처리하기 애매할듯
[0,1,2,3,4,5] [0,1,2,3,4,5] [5,0,1,2,3,4] [5,0,1,2,3,4]
1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4
딱히 값을 이용해서 더 빠르게 찾을 방법이 생각나지 않는데, 값-인덱스 기법은 대체로 비교보다는 동치연산에 쓰이므로..
[4,5,6,7,0,1,2]
최소나 최대값이라도 알면 .. 지금 문제는, 이분탐색을 해야 하는데 정렬이 되어있지 않다는 것.
[4,5,6,7,8,0,1,2,3]
이런 경우 1을 찾으라 하면?
- 큰 수인 8을 먼저 본 경우
더 작은 수인 1을 찾으려 계속 왼쪽으로 가다가 못 찾고 끝난다. 2. 작은 수인 0을 먼저 본 경우 오른쪽 구간에서 성공적으로 1을 찾을 것이다.
그렇지만 이것은 pivot을 기준으로 양 옆을 찾은 덕분이고, 7과 8로 탐색을 시작한다면 둘 다 실패하게 된다.
그럼 어떻게 해야 하나?
- pivot을 일단 찾는 방법:
- 왼쪽 수가 오른쪽 수보다 큰 것을 범위를 줄여가며 찾는다.
회전이 되어있다면 오른쪽 끝 수가 왼쪽 끝 수보다 작다.
- 양 끝에서 다른 탐색을 하는 방법:
아, 지금 생각해보니 일단 target이 왼쪽 끝 수보다 크다면 그 쪽에 있을거고, 아니라면 오른쪽 파트에 있을 것이다.
증가하는 이분 탐색:
- target 찾으면 종료
- 오른쪽으로 갔는데 숫자 감소하면 왼쪽 탐색
- 왼쪽으로 갔는데 target보다 작으면 오른쪽 탐색
- 오른쪽으로 갔는데 target보다 크면 왼쪽 탐색
감소하는 이분 탐색
- target 찾으면 종료
- 왼쪽으로 갔는데 숫자 증가하면 오른쪽 탐색
- 왼쪽으로 갔는데 target보다 작으면 오른쪽 탐색
- 오른쪽으로 갔는데 target보다 크면 왼쪽 탐색
7트만에 성공..
도무지 이분탐색의 구간 엣지처리가 익숙해지질 않는다..
py3 solution
def search(nums: List[int], target: int) -> int:
import math
first = nums[0]
last = nums[-1]
cnt = len(nums)
if target >= nums[0]:
le = 0
ri = len(nums)
prev = -99999
while (le <= ri):
mid = math.floor((le + ri) / 2)
if (mid >= cnt):
return -1
cur = nums[mid]
print('1le',le,'ri',ri,'mid',mid, 'cur',cur)
if (cur == target):
return mid
if (cur < first):
ri = mid
elif (cur > target):
ri = mid
elif (cur < target):
le = mid + 1
if (mid == prev):
return -1
prev = mid
return le
le = -1
ri = len(nums) - 1
prev = -99999
while (le <= ri):
mid = math.ceil((le + ri) / 2)
cur = nums[mid]
print('2le',le,'ri',ri,'mid',mid, 'cur',cur)
if (cur == target):
return mid
if (cur > last):
le = mid
elif (cur > target):
ri = mid - 1
elif (cur < target):
le = mid
if (mid == prev):
return -1
prev = mid
return le
Comments