leetcode 34. 정렬 배열 에서 요소 의 첫 번 째 와 마지막 위 치 를 찾 습 니 다 (자바 버 전)
오름차 순 으로 배 열 된 정수 배열
nums 과 목표 치 target 를 지정 합 니 다.주어진 목표 값 이 배열 의 시작 위치 와 끝 위 치 를 찾 습 니 다.당신 의 알고리즘 시간 복잡 도 는 반드시 O (log n) 등급 이 어야 합 니 다.
배열 에 목표치 가 존재 하지 않 으 면 되 돌려 줍 니 다
[-1, -1].예시 1:
입력: nums = [5, 7, 7, 8, 8, 10], target = 8 출력: [3, 4]
예시 2:
입력: nums = [5, 7, 7, 8, 8, 10], target = 6 출력: [- 1, - 1]
문제 풀이
이런 문 제 는 아주 좋 습 니 다. 만약 에 이 문제 가 없 으 면 제 가 실제 에서 이 문 제 를 만나면 생각 은 2 분 에 같은 요소 중의 하 나 를 찾 은 다음 에 각각 앞으로, 뒤로 차례대로 일치 하여 첫 번 째 와 마지막 위 치 를 찾 을 때 까지 하 는 것 이 라 고 생각 합 니 다.그러나 이렇게 하면 최 악의 경우 알고리즘 의 시간 복잡 도 는 O (n) 이다.한편, 문 제 는 알고리즘 시간 복잡 도 는 반드시 O (log n) 등급 이 어야 하기 때문에 자신 을 강요 하면 다음 과 같은 알고리즘 이 생 긴 다.알고리즘 의 기본 구 조 는 물론 2 분 으로 찾 아야 합 니 다. 다만 첫 번 째 2 분 으로 찾 은 후에 첫 번 째 로 포 지 셔 닝 한 목표 요소 의 양쪽 을 각각 2 분 으로 찾 아 목표 요소 의 경 계 를 찾 아야 합 니 다.알고리즘 사상 도 간단 하지만 인 코딩 실현 에 있어 어느 정도 어려움 이 있다.
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums == null || nums.length == 0) return new int[]{-1, -1};
int mid = 0, low = 0, high = nums.length-1;
while(low <= high){
mid = (low+high) >> 1;
if(nums[mid] == target) break;
else if(nums[mid] < target) low = mid + 1;
else high = mid - 1;
}
if(low > high) return new int[]{-1, -1};
int[] result = new int[2];
if(nums[low] <= target) result[0] = BSR(nums, low, mid, target)[0];
if(nums[high] >= target) result[1] = BSR(nums, mid, high, target)[1];
return result;
}
private int[] BSR(int[] a, int low, int high, int target){
int mid;
while(low <= high){
mid = (low+high) >> 1;
if(a[mid] == target){
if(a[low] == a[high]) return new int[]{low, high};
if(a[low] < target) return BSR(a, low+1, mid, target);
if(a[high] > target) return BSR(a, mid, high-1, target);
}
else if(a[mid] < target) low = mid + 1;
else high = mid - 1;
}
return new int[]{-1, -1};
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
