Search For A Range
public class Solution {
public int[] searchRange(int[] A, int target) {
// Start typing your Java solution below
// DO NOT write main() function
int[] res = {-1, -1};
if(A.length == 0)
return res;
int begin = 0;
int end = A.length - 1;
while(begin < end){
int mid = begin + (end - begin) / 2;
if(A[mid] >= target)
end = mid;
else
begin = mid + 1;
}
if(A[begin] != target)
return res;
else
res[0] = begin;
begin = 0;
end = A.length - 1;
while(begin < end){
int mid = begin + (end - begin + 1) / 2;// pay attention to +1 here, eg. {0, 1, 2, 3}, +1 makes mid to 2, not 1.
if(A[mid] <= target)
begin = mid;
else
end = mid - 1;
}
if(A[end] != target)
return res;
else
res[1] = end;
return res;
}
}
Recursive:
public int[] searchRange(int A[], int n, int target) {
// Start typing your JAVA solution below
// DO NOT write int main() function
int[] result = {-1, -1};
result[0] = findPosition(A, 0, n - 1, target, true);
result[1] = findPosition(A, 0, n - 1, target, false);
return result;
}
int findPosition(int A[], int begin, int end, int target, boolean leftFlag) {
if (begin > end)
return -1;
int middle = (begin + end) / 2;
if (A[middle] == target) {
int position;
if (leftFlag) {
position = findPosition(A, begin, middle - 1, target, leftFlag);
} else {
position = findPosition(A, middle + 1, end, target, leftFlag);
}
return (position == -1) ? middle : position;
} else if (A[middle] < target) {
return findPosition(A, middle + 1, end, target, leftFlag);
} else {
return findPosition(A, begin, middle - 1, target, leftFlag);
}
}
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return
[-1, -1]
. For example, Given
[5, 7, 7, 8, 8, 10]
and target value 8, return [3, 4]
.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.