회전 정렬 배열 검색
오름차 순 으로 정렬 된 배열 이 미리 알 수 없 는 한 점 에서 회전 했다 고 가정 합 니 다.
배열 [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
코드:
class Solution {
public:
int search(vector& nums, int target) {
if (nums.empty())return -1;
int low = 0, high = nums.size() - 1, mid;
while (low < high)
{
mid = (high + low) / 2;
if (nums[mid] == target)return mid;
if (nums[mid] >= nums[low])
{
if (target >= nums[low] && target < nums[mid])high = mid - 1;
else low = mid + 1;
}
else
{
if (target>nums[mid] && target <= nums[high])low = mid + 1;
else high = mid - 1;
}
}
if (nums[low] == target)return low;
return -1;
}
}; PS：
나 는 대학 3 학년 때 실습 을 구 할 때 한 회 사 를 면접 하여 이 문 제 를 풀 었 다.
그때 저 는 첫 번 째 느낌 이 O (n) 의 알고리즘 이 었 습 니 다. 면접 관 이 저 에 게 O (log n) 의 알고리즘 이 있 느 냐 고 물 었 습 니 다. 저 는 대충 생각 을 말 했 습 니 다.
면접 관 은 나 에 게 구체 적 인 분류 상황 을 열거 하 라 고 했 지만 나 는 성공 하지 못 했다.
사실 어렵 지 않 아 요. 정말 어렵 지 않 아 요. 그런데 면접 이 좀 긴장 되 고 정리 가 안 돼 요.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
