정렬 배열 에서 요소 의 첫 번 째 와 마지막 위 치 를 찾 습 니 다 (힘 단추 34)
1567 단어 알고리즘 문제
오름차 순 으로 배 열 된 정수 배열 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]
문제 풀이 의 사고 방향.
제목 에서 시간 복잡 도 는 O (log n) 등급 이 어야 하기 때문에 우 리 는 2 분 검색 을 사용 하고 2 분 검색 을 사용 하여 목표 수 를 찾 은 후에 왼쪽 에서 오른쪽으로 계속 검색 하여 좌우 경 계 를 확인 해 야 한다 고 강조 했다.
경계 인지 아 닌 지 어떻게 판단 합 니까?왼쪽 포인터 의 왼쪽 값 이 목표 수 와 같 지 않 으 면 왼쪽 경 계 를 확정 합 니 다.마찬가지 로 오른쪽 포인터 의 오른쪽 값 이 목표 수 와 같 지 않 으 면 오른쪽 경 계 를 확정 한 것 이다.주의: 배열 의 경 계 를 넘 지 않도록 판단 해 야 합 니 다.
상위 코드
public static int[] searchRange(int[] nums, int target) {
if (nums.length == 0)
return new int[] { -1, -1 };
int l = 0;
int r = nums.length - 1;
int k = 0;
int flag = -1;
while (l <= r) {
k = l + (r - l) / 2;
if (nums[k] < target) {
l = k + 1;
} else if (nums[k] > target) {
r = k - 1;
} else {
flag = 0;
break;
}
}
if (flag == 0) {
l = k;
r = k;
while ((l != 0 && nums[l - 1] == target) || (r != (nums.length - 1) && nums[r + 1] == target)) {
if (l != 0 && nums[l - 1] == target)
l--;
if ((r != (nums.length - 1) && nums[r + 1] == target))
r++;
}
return new int[] { l, r };
}
return new int[] { -1, -1 };
}
flag 가 - 1 과 같 을 때 nums 배열 에 목표 값 이 없 음 을 나타 내 고 flag 가 0 과 같 을 때 nums 배열 에 목표 값 이 있 음 을 나타 내 고 좌우 경 계 를 확정 하면 됩 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[못 푼 문제] 백준 10989번sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
