Find Minimum in Rotated Sorted Array
서로 다른 정수로 이루어진 목록을 오름차순으로 정렬한 다음 회전했습니다. 즉, 앞에서 일부 요소를 가져와 같은 순서로 뒤에 옮겼습니다. 옮긴 요소의 수는 0일 수도 있습니다. 예를 들어, [2, 5, 9, 11, 13, 15, 17]을 3만큼 회전하면 [11, 13, 15, 17, 2, 5, 9]가 됩니다. 회전된 목록 nums가 주어집니다. O(log n) 시간에 가장 작은 값을 반환하세요.
함수
- numsinteger-array
- 회전된 정렬된 서로 다른 정수 목록
- 반환값integer
- nums에서 가장 작은 값
제약 조건
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104-
nums의 모든 값은 서로 다릅니다. nums는 어떤k만큼 회전된 오름차순 리스트이며,0 ≤ k < nums.length입니다.k = 0이면 회전되지 않은 상태입니다.
예제
- 입력
- nums = [11, 13, 15, 17, 2, 5, 9]
- 출력
- 2
- 설명
- 값은 11에서 17까지 올라간 다음 2까지 내려가며, 여기서 두 번째 구간이 시작됩니다. 검색 과정에서 인덱스 3의 17 > 9를 확인하므로 최솟값은 그 오른쪽에 있습니다. 그런 다음 5 ≤ 9와 2 ≤ 5에 따라 범위가 인덱스 4 하나만 남을 때까지
hi가 뒤로 이동하고, 그곳에는 2가 있습니다.
- 입력
- nums = [4, 7, 10, 12]
- 출력
- 4
- 설명
- 이 목록은 0만큼 회전했으므로 여전히 정렬되어 있으며 최솟값은 첫 번째 값입니다. 모든 중간값은 마지막 값보다 작거나 같으므로
hi는 인덱스 0에 도달할 때까지 계속 왼쪽으로 이동하며, 인덱스 0에는 4가 있습니다.
- 입력
- nums = [30, -6, 0, 8, 19]
- 출력
- -6
- 설명
- 네 개의 값이 앞에서 뒤로 이동했으므로, 가장 큰 값인 30이 이제 맨 앞에 오고 최솟값인 -6은 인덱스 1에 있습니다. 검색 범위는 인덱스 0과 1로 줄어들고, 30 > -6임을 확인한 뒤
lo를 1로 이동합니다.
제출 시 숨은 테스트 +17개
후속 질문
정렬하지 않고 nums에서 k번째로 작은 값을 O(log n) 시간에 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
정렬된 목록에서는 모든 값이 바로 앞의 값보다 큽니다. 회전으로 인해 그 순서가 정확히 한 곳에서 깨집니다. 가장 작은 값은 그 위치를 기준으로 어디에 있을까요?
범위의 중간 값과 마지막 값을 비교하세요. 중간 값이 더 크다면 그 이후 어딘가에서 값이 내려가야 합니다. 중간 값이 더 작다면 중간부터 끝까지 내려가는 부분 없이 계속 올라갑니다.
lo와hi가 최솟값을 둘러싸도록 유지합니다.nums[mid] > nums[hi]이면lo를mid + 1로 옮기고, 그렇지 않으면mid자체가 최솟값일 수 있으므로hi를mid로 옮깁니다.lo와hi가 같아지면 멈춥니다.
풀이
회전 정렬된 목록은 증가하는 두 구간, [11, 13, 15, 17]과 [2, 5, 9]으로 이루어집니다. 최솟값은 두 번째 구간의 첫 번째 값으로, 값이 감소하는 유일한 지점 바로 다음에 있습니다. 목록을 순회하면 O(n)에 그 감소 지점을 찾습니다. 중간값 하나를 구간의 마지막 값과 비교하면 중간값이 감소 지점의 어느 쪽에 있는지 알 수 있으므로, 이진 검색으로 O(log n)에 찾을 수 있습니다.
값이 감소할 때까지 걷기
핵심 아이디어
정렬된 목록에서는 각 값이 그 앞에 있는 값보다 큽니다. 목록을 회전해도 두 구간은 정렬된 상태를 유지하며, 딱 한 곳에서만 이 조건이 깨집니다. 가장 큰 값 다음에 가장 작은 값이 오는 곳입니다. 따라서 왼쪽에서 오른쪽으로 순회하면서 왼쪽 이웃보다 작은 첫 번째 값을 반환하세요. 그런 값이 없다면 목록은 0만큼 회전한 것이며 최솟값은 nums[0]입니다.
[11, 13, 15, 17, 2, 5, 9]에서는 순회가 13, 15, 17을 지나갑니다. 각각 앞에 있는 값보다 크며, 인덱스 4에서 2가 17보다 작은 지점에서 멈춥니다. 하락 지점에서 멈추기 때문에 모든 값의 최솟값을 구하는 것보다는 이미 낫지만, 하락 지점은 어디에나 있을 수 있습니다. [2, 3, 4, 5, 6, 7, 8, 1]처럼 한 요소만큼 회전한 경우 순회는 목록 전체를 읽습니다. 요소 5000개에 비교 5000회가 필요한 반면, 이진 탐색은 13회면 됩니다.
알고리즘
i가 1부터n-1까지인 각 인덱스에 대해nums[i]와nums[i-1]를 비교합니다.nums[i] < nums[i-1]이면nums[i]를 반환합니다. 두 번째 구간이 그 지점에서 시작합니다.- 루프가 끝나면 목록은 회전되지 않은 것입니다.
nums[0]을 반환합니다.
def findMin(nums):
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
return nums[i] # the only drop: the second run starts here
return nums[0] # no drop: the list was not rotated마지막 값과 비교하는 이진 검색
핵심 아이디어
한 가지 불변 조건을 유지하세요. 최솟값은 lo와 hi 사이에 있으며, 양 끝을 포함합니다. 처음에는 그 범위가 전체 목록입니다. 가운데 값을 확인하고 범위의 마지막 값인 nums[hi]와 비교하세요.
nums[mid] > nums[hi]이면 mid와 hi 사이 어딘가에서 값이 감소하며, 최솟값은 그 감소 지점 바로 다음 값이므로 mid의 오른쪽에 있습니다. 따라서 lo = mid + 1로 설정하세요. 그렇지 않으면 nums[mid] < nums[hi]입니다(값은 서로 다릅니다). 따라서 nums[mid..hi]는 감소하는 부분 없이 증가합니다. 그러면 최솟값은 nums[mid]이거나 그 앞에 있으므로 hi = mid로 설정하세요. mid를 건너뛰지 마세요. 그 값이 최솟값일 수도 있습니다. 어느 쪽으로 이동해도 불변 조건이 유지되고 범위가 줄어들며, lo와 hi가 같아지면 남은 값 하나가 최솟값입니다.
첫 번째 예시인 [11, 13, 15, 17, 2, 5, 9]를 추적해 보세요. 인덱스 0부터 6까지의 범위에서 가운데 인덱스는 3이고 값은 17입니다. 이는 nums[6] = 9보다 크므로 lo는 4가 됩니다. 인덱스 4부터 6까지의 범위에서 가운데 인덱스는 5이고 값은 5로, 9보다 크지 않으므로 hi는 5가 됩니다. 인덱스 4부터 5까지의 범위에서 가운데 인덱스는 4이고 값은 2로, 5보다 크지 않으므로 hi는 4가 됩니다. nums[4] = 2를 반환합니다.
매 단계마다 범위가 절반으로 줄어드므로 반복문은 최대 약 log2(n)회 실행됩니다. 원소가 5000개라면 13단계이며, 추가 메모리는 인덱스 두 개뿐입니다.
알고리즘
lo = 0및hi = n-1을 설정합니다.lo < hi인 동안mid = lo + (hi - lo) / 2를 계산합니다.nums[mid] > nums[hi]이면lo = mid + 1을 설정합니다.- 그렇지 않으면
hi = mid를 설정합니다. - 루프가 끝나면
nums[lo]를 반환합니다.
def findMin(nums):
lo, hi = 0, len(nums) - 1 # the minimum sits in nums[lo..hi]
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the values drop after mid, so the minimum is right of it
else:
hi = mid # nums[mid..hi] climbs: the minimum is at mid or left of it
return nums[lo]
함정과 경계 사례
루프는 네 줄이며, 각 줄마다 그럴듯하지만 잘못된 버전이 있습니다.
- 두 번째 분기에서
hi = mid - 1을 작성하는 경우. 이 분기는mid가 최솟값 자체일 수 있을 때 실행됩니다.[3, 1, 2]에서 중간값 1은 2보다 크지 않으므로hi는 0으로 줄어들고 함수는 3을 반환합니다. lo ≤ hi조건으로 반복하는 경우.lo가hi와 같아지면mid도 둘 다와 같고,nums[mid] > nums[hi]는 거짓이며,hi = mid는 아무것도 바꾸지 않습니다. 루프가 끝나지 않습니다. 범위에 요소가 하나 남으면 멈추도록lo < hi를 사용하세요.nums[hi]대신nums[lo]와 비교하는 경우. 회전되지 않은 목록[1, 2, 3, 4, 5]에서 중간값 3은nums[0] = 1보다 크므로, 최솟값이 오른쪽에 있는 것처럼 보입니다. 따라서 탐색은 인덱스 0에 있는 실제 최솟값에서 멀어지는 방향으로 이동하고 4를 반환합니다.nums[lo]대신lo를 반환하는 경우. 문제에서 요구하는 것은 값입니다. 인덱스는 다른 질문에 대한 답입니다(회전 횟수에 관한 FAQ 참조).- 목록이 회전되었다고 가정하는 경우. 0회 회전도 허용되며, 다른 처리 없이 감소 지점을 찾는 코드는 끝을 벗어나 읽거나 아무것도 반환하지 않습니다. 감소 지점이 없으면
nums[0]을 반환하세요.
자주 묻는 질문4
회전된 정렬 배열에서 최솟값을 찾는 시간 복잡도는 얼마인가요?
이진 검색을 사용하면 시간은 O(log n)이고 추가 공간은 O(1)입니다. 각 단계에서 범위의 절반을 남기므로, 요소가 5000개인 목록은 비교를 최대 13번만 하면 됩니다. 감소 지점을 찾는 순회는 O(n)입니다. 최솟값이 끝에 있으면 모든 요소를 읽습니다.
왜 nums[mid]를 nums[lo]가 아니라 nums[hi]와 비교하나요?
nums[hi]는 최솟값이 어느 쪽에 있는지 항상 결정하지만, nums[lo]는 그렇지 않기 때문입니다. nums[mid] > nums[hi]이면 값은 mid와 hi 사이에 있어야 합니다. 그렇지 않으면 nums[mid..hi]는 증가하며 최솟값은 mid 또는 그 이전에 있습니다. nums[lo]의 경우 nums[mid] > nums[lo]라는 결과는 최솟값이 nums[lo]인 회전되지 않은 리스트와 최솟값이 mid의 오른쪽에 있는 회전된 리스트 모두에 해당합니다.
정렬된 배열이 몇 번 회전했는지 어떻게 알 수 있나요?
동일한 이진 탐색을 수행하고, nums[lo] 대신 최솟값의 인덱스인 lo를 반환하세요. 회전을 마지막 요소를 맨 앞으로 이동하는 것으로 센다면, 해당 인덱스가 회전 횟수입니다. 이 문제처럼 첫 번째 요소를 맨 뒤로 이동하는 것으로 센다면, 횟수는 (n - lo) mod n입니다. [11, 13, 15, 17, 2, 5, 9]에서는 최솟값이 인덱스 4에 있으며, 7에서 4를 빼면 이동한 값의 개수인 3이 됩니다.
배열에 중복된 값이 있어도 이진 검색이 작동하나요?
변경되지 않은 것은 아닙니다. [2, 2, 2, 0, 2]에서는 nums[mid]가 nums[hi]와 같을 수 있으며, 이 경우 어느 쪽도 배제할 수 없습니다. 이때 hi = hi - 1로 범위를 줄이는 것은 안전합니다. nums[hi]의 복사본이 mid에 남아 범위 안에 있기 때문입니다. 하지만 같은 값들 사이에 더 작은 값 하나가 숨겨진 목록에서는 O(n)의 비용이 듭니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def findMin(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [11, 13, 15, 17, 2, 5, 9]
기대값
2