Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Follow up: Could you write an algorithm with O(log n) runtime complexity?
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
문제 풀이:
투포인터를 사용한다. 동일한 값을 발견하면 범위를 찾는다.
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] answer = new int[2];
answer[0] = -1;
answer[1] = -1;
int start = 0, end = nums.length-1;
while(start <= end){
int mid = (start + end)/2;
if(nums[mid] < target){
start = mid+1;
}else if(nums[mid] > target){
end = mid-1;
}else {
int begin = mid, after = mid;
while(--begin > -1 && ++after < nums.length){
if(nums[begin]!= target || nums[after] != target){
break;
}
}
while(begin> -1){
if(nums[begin] != target){
break;
}
begin--;
}
while(after<nums.length){
if(nums[after]!=target){
break;
}
after++;
}
answer[0] = begin+1;
answer[1] = after-1;
break;
}
}
return answer;
}
}
'알고리즘 문제풀이 > leetcode' 카테고리의 다른 글
[leetcode 29] Divide Two Integers (0) | 2020.11.13 |
---|---|
[leetcode 14] Longest Common Prefix (0) | 2020.11.13 |
[leetcode 23] Merge k Sorted Lists (0) | 2020.11.12 |
[leetcode 54] Spiral Matrix (0) | 2020.11.10 |
[leetcode 28] Implement strStr() (0) | 2020.11.10 |
댓글