leetcode 33 - 회전 정렬 배열 검색
10713 단어 leetcode
제목 의 뜻 을 약술 하 다.
오름차 순 으로 정렬 된 배열 이 미리 알 수 없 는 한 점 에서 회전 했다 고 가정 합 니 다.(예 를 들 어 배열 [0, 1, 2, 4, 5, 6, 7] 은 [4, 5, 6, 7, 0, 1, 2] 로 변 할 수 있다.주어진 목표 값 을 검색 합 니 다. 배열 에 이 목표 값 이 존재 하면 색인 을 되 돌려 줍 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.너 는 배열 에 중복 되 는 요소 가 존재 하지 않 는 다 고 가정 할 수 있다.당신 의 알고리즘 시간 복잡 도 는 반드시 O (log n) 등급 이 어야 합 니 다.
예시 1:
입력: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 출력: 4
예시 2:
입력: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 출력: - 1
문제 풀이 분석
: , ,
. ,
; , , .
:
: S(n) = S(n/2) + log(n/2), S(1) = 1;
: n = 2^k, S(2^k) = S(2^(k-1)) + (k - 1)log29
,S(n) = O(logn * logn)
참조 코드
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while(left < right) {
int mid = (left + right) >> 1;
if(nums[mid] == target) return mid;
if(nums[mid] < nums[left]) {
int idx = binarySearch(nums,mid,right,target);
if(idx != -1) return idx;
right = mid;
} else {
int idx = binarySearch(nums,left,mid,target);
if(idx != -1) return idx;
left = mid + 1;
}
}
return -1;
}
public int binarySearch(int[] nums, int left, int right, int target) {
int low = left;
int top = right;
while(low < top) {
int mid = (low + top) >> 1;
if(nums[mid] < target) {
low = mid + 1;
} else {
top = mid;
}
}
return (low < right && nums[low] == target) ? low : -1;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
