[이진 검색]회전된 목록에서 가장 큰 수 찾기
설명
오름차순으로 정렬되고 일부 피벗점에서 회전되는 고유 정수 목록nums이 제공됩니다. 회전된 목록에서 최대 개수를 찾습니다.
O(log*n*)로 해결할 수 있나요?
제약 조건:
n ≤ 100,000 여기서 n는 nums의 길이입니다. 예 1
입력
arr = [6, 7, 8, 1, 4]
산출
arr = [6, 7, 8, 1, 4]
설명
The original sorted array of [1, 4, 6, 7, 8] was rotated at index 2 and results in the input array [6, 7, 8, 1, 4,]. And the largest number is 8.
예 2
입력
arr = [1, 2, 3]
산출
3
예 3
입력
arr = [1]
산출
1
예시 4
입력
arr = [10, 1, 2, 3, 4, 7]
산출
10
직관
(arr[mid+1] < arr[mid]) , mid 는 가장 큰 값 인덱스 구현
import java.util.*;
class Solution {
// Time=O(logn), space=O(1)
public int solve(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 0....mid, mid+1....right
if (mid + 1 < arr.length && arr[mid + 1] < arr[mid]) {
return arr[mid];
}
if (arr[left] <= arr[mid]) {
// left side sorted
// 8,9,10,4,5,6
left = mid + 1;
} else {
right = mid;
}
}
return arr[left];
}
}
시간 복잡도
import java.util.*;
class Solution {
// Time=O(logn), space=O(1)
public int solve(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 0....mid, mid+1....right
if (mid + 1 < arr.length && arr[mid + 1] < arr[mid]) {
return arr[mid];
}
if (arr[left] <= arr[mid]) {
// left side sorted
// 8,9,10,4,5,6
left = mid + 1;
} else {
right = mid;
}
}
return arr[left];
}
}
Reference
이 문제에 관하여([이진 검색]회전된 목록에서 가장 큰 수 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/find-the-largest-number-in-a-rotated-list-3f7m텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
