给出一个有序数组，请在数组中找出目标值的起始位置和结束位置
你的算法的时间复杂度应该在O(log n)之内
如果数组中不存在目标，返回[-1, -1].
例如：
给出的数组是[50, 70, 70, 80, 80, 100]，目标值是80,
返回[3, 4].
[编程题]求目标值的区间
/* 调用两次二分 */
public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] searchRange (int[] A, int target) {
// write code here
int left = find(A, target, true);
int right = find(A, target, false);
return new int[]{left, right};
}
public int find(int[] A, int target, boolean isLeft) {
int l = 0;
int r = A.length - 1;
int m = 0;
int res = -1;
while (l <= r) {
m = l + (r - l) / 2;
if (A[m] < target) {
l = m + 1;
} else if (A[m] > target) {
r = m - 1;
} else {
res = m;
if (isLeft) {
r = m - 1;
} else {
l = m + 1;
}
}
}
return res;
}
}
发表于 2021-09-28 15:14:01
回复(0)
import java.util.*;
public class Solution {
int min = -1, max = -1;
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] searchRange(int[] nums, int target) {
searchHelper(nums, 0, nums.length - 1, target);
return new int[]{min, max};
}
public void searchHelper(int[] nums, int left, int right, int target) {
if (right < left) {
return;
}
int mid = (right - left) / 2 + left;
// 如果中点值小于target，则在右边找
if (nums[mid] < target) {
searchHelper(nums, mid + 1, right, target);
}
// 如果中点値大于target，则在左边找
else if (nums[mid] > target) {
searchHelper(nums, left, mid - 1, target);
}
// 否则两边都得找
else {
if (min == -1 && max == -1) {
min = mid;
max = mid;
}
if (mid < min) {
min = mid;
}
if (mid > max) {
max = mid;
}
searchHelper(nums, left, mid - 1, target);
searchHelper(nums, mid + 1, right, target);
}
}
}
发表于 2020-08-01 11:01:28
回复(0)
public int[] searchRange (int[] A, int target) {
int[] result = new int[]{-1, -1};
if(A == null || A.length < 1) {
return result;
}
searchRange(A, 0, A.length - 1, target, result);
if(result[1] == -1) {
result[1] = result[0];
}
return result;
}
public void searchRange (int[] A, int start, int end, int target, int[] result) {
if(start > end) {
return;
}
if(start == end) {
if(A[start] == target) {
put(start, result);
}
return;
}
int mid = (start + end) / 2;
//如果符合条件，两头查找
if(target >= A[start] && target <= A[mid]) {
//mid在正中或者偏向左边，所以mid计入左侧，防止2个时迭代没有更进一步导致死循环
searchRange(A, start, mid, target, result);
}
if(target >= A[mid + 1] && target <= A[end]) {
searchRange(A, mid + 1, end, target, result);
}
}
public void put(int index, int[] result) {
//优先设置0位置
if(result[0] == -1) {
result[0] = index;
return;
}
if(result[1] == -1) {
//如果位置1小于位置0，交换
if(index < result[0]) {
result[1] = result[0];
result[0] = index;
}
result[1] = index;
return;
}
//保证put的值是最大或者最小的
if(index < result[0]) {
result[0] = index;
} else if(index > result[1]){
result[1]= index;
}
}
编辑于 2020-06-09 21:55:11
回复(0)
详细过程见我CSDN博客：https://blog.csdn.net/weixin_42047723/article/details/93721826
我们先来看看时间复杂度为O(n)的算法，分别从左遍历和从右遍历数组，找到目标数的第一个下标位置分为是要求解的目标值的起始和结束位置
public class Solution { public int[] searchRange(int[] A, int target) { int res[] = new int[2]; res[0] = -1; res[1] = -1; //向左找 for(int i = 0 ; i < A.length; i++){ if(A[i] == target){ res[0] = i; break; } } //向右找 for(int i = A.length - 1 ; i >= 0; i--){ if(A[i] == target){ res[1] = i; break; } } return res; } }
若要求时间复杂度为O(log n)，我们可以利用二分查找的方法，该算法的时间复杂度为O(log n)。通过两次二分法查找，找到目标值的左边界和右边界，需要对二分查找法稍微加以修改。当查找右边界时，即当A[middle]小于等于目标数target时，low游标自增1继续往右走。同理当查找左边界时，即当A[middle]大于等于目标数target时，high游标自减1继续往左走。
public class Solution { public int[] searchRange(int[] A, int target) { int len = A.length; int res[] = new int[2]; res[0] = -1; res[1] = -1; int low1 = 0, high1 = len - 1; //查找右边界 while(low1 <= high1){ int middle1 = (low1 + high1) / 2; if(A[middle1] <= target) low1 = middle1 + 1; else high1 = middle1 - 1; } int low2 = 0, high2 = len - 1; //查找左边界 while(low2 <= high2){ int middle2 = (low2 + high2) / 2; if(A[middle2] >= target) high2 = middle2 - 1; else low2 = middle2 + 1; } if(low2 <= high1){ res[0] = low2; res[1] = high1; } return res; } }
编辑于 2019-06-26 19:09:58
回复(1)
public class Solution {
public int[] searchRange(int[] A, int target) {
int low = 0;
int high = A.length;
int mid;
while(low < high) {
mid = (low + high) >>> 1;
if(A[mid] >= target){
high = mid;
} else {
low = mid + 1;
}
}
int start = low;
if(start == A.length || A[start] != target) {
return new int[] {-1, -1};
}
low = start;
high = A.length;
while(low < high) {
mid = (low + high) >>> 1;
if(A[mid] > target) {
high = mid;
} else {
low = mid + 1;
}
}
int end = low - 1;
return new int[] {start, end};
}
}
public class Solution {
public int[] searchRange(int[] A, int target) {
int low = 0;
int high = A.length;
int mid;
while(low < high) {
mid = (low + high) >>> 1;
if(A[mid] >= target){
high = mid;
} else {
low = mid + 1;
}
}
int start = low;
if(start == A.length || A[start] != target) {
return new int[] {-1, -1};
}
low = start;
high = A.length;
while(low < high) {
mid = (low + high) >>> 1;
if(A[mid] > target) {
high = mid;
} else {
low = mid + 1;
}
}
int end = low - 1;
return new int[] {start, end};
}
}
public int[] searchRange(int[] A, int target) {
int low = 0;
int high = A.length;
int mid;
while(low < high) {
mid = (low + high) >>> 1;
if(A[mid] >= target){
high = mid;
} else {
low = mid + 1;
}
}
int start = low;
if(start == A.length || A[start] != target) {
return new int[] {-1, -1};
}
low = start;
high = A.length;
while(low < high) {
mid = (low + high) >>> 1;
if(A[mid] > target) {
high = mid;
} else {
low = mid + 1;
}
}
int end = low - 1;
return new int[] {start, end};
}
}
public class Solution {
public int[] searchRange(int[] A, int target) {
int low = 0;
int high = A.length;
int mid;
while(low < high) {
mid = (low + high) >>> 1;
if(A[mid] >= target){
high = mid;
} else {
low = mid + 1;
}
}
int start = low;
if(start == A.length || A[start] != target) {
return new int[] {-1, -1};
}
low = start;
high = A.length;
while(low < high) {
mid = (low + high) >>> 1;
if(A[mid] > target) {
high = mid;
} else {
low = mid + 1;
}
}
int end = low - 1;
return new int[] {start, end};
}
}
发表于 2019-06-15 16:21:04
回复(0)
public class Solution {
int res[]; //保证结果
public int[] searchRange(int[] A, int target) {
int low=0;
int high=A.length-1;
int start=-1,end=-1;
int times=0;
while(low<=high) //二分查找
{
int mid =(low+high)/2;
if (A[mid]>target) high=mid-1;
else if(A[mid]<target) low=mid+1;
//相等时候，我就只能暴力了
else
{
for(int i=low;i<=high;i++)
{
if(A[i]==target && times==0) { start=i; }
if(A[i]==target) times++;
} //end for
end= start + times-1;
return res=new int[]{start,end};
}
}
return res=new int[]{start,end};
}
}
编辑于 2018-04-05 11:19:28
回复(0)
public class Solution {
public int[] searchRange(int[] A, int target) {
int lo=0,hi=A.length-1;
int left=-1,right=-1;
while(lo<=hi){
int mid=(hi-lo)/2+lo;
if(target<A[mid]){
hi=mid-1;
}else if(target>A[mid]){
lo=mid+1;
}else{
left=mid;
right=mid;
if(A[left]==target&&left-1>=lo&&A[left-1]==target){
int lo1=lo,hi1=mid-1;
while(lo1<=hi1){
int leftmid=(hi1-lo1)/2+lo1;
if(A[leftmid]<target){
lo1=leftmid+1;
}else if(A[leftmid]>target){
hi1=leftmid-1;
}else{
if(leftmid-1>=lo&&A[leftmid-1]==target){
hi1=leftmid-1;
}else{
left=leftmid;
break;
}
}
}
}
if(A[right]==target&&right+1<=hi&&A[right+1]==target){
int lo2=mid+1,hi2=hi;
while(lo2<=hi2){
int rightmid=(hi2-lo2)/2+lo2;
if(A[rightmid]<target){
lo2=rightmid+1;
}else if(A[rightmid]>target){
hi2=rightmid-1;
}else{
if(rightmid+1<=hi&&A[rightmid+1]==target){
lo2=rightmid+1;
}else{
right=rightmid;
break;
}
}
}
}
break;
}
}
int[] result={left,right};
return result;
}
}
发表于 2018-04-03 11:30:06
回复(1)
public class Solution {
public int[] searchRange(int[] A, int target) {
int lastlower, firstbigger;
int left = 0;
int right = A.length-1;
while(left <= right) {
int mid = (left + right) / 2;
if(A[mid] <= target)
left = mid + 1;
else
right = mid - 1;
}
firstbigger = right + 1;
left = 0;
right = A.length-1;
while(left <= right) {
int mid = (left + right) / 2;
if(A[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
lastlower = left - 1;
if((firstbigger - lastlower) > 1)
return new int[]{lastlower + 1, firstbigger - 1};
else
return new int[]{-1, -1};
}
}
发表于 2017-06-05 19:05:46
回复(0)
public class Solution {
public int[] searchRange(int[] A, int target) {
int low = 0, high = A.length - 1, mid = 0;
int start = - 1, end = - 1;
while (low <= high) {
mid = (low + high) / 2;
if(A[mid] < target) low = mid + 1;
else if(A[mid] > target) high = mid - 1;
else {
start = end = mid;
while (start >= 0 && A[start] == target) start --;
while (end < A.length && A[end] == target) end ++;
return new int[] {start + 1, end - 1};
}
}
return new int[] {start, end};
}
}
发表于 2017-03-26 17:08:58
回复(7)
public class Solution { public int[] searchRange(int[] A, int target) { int start = Solution.firstGreaterEqual(A, target); if (start == A.length || A[start] != target) { return new int[]{-1, -1}; } return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1}; } //find the first number that is greater than or equal to target. //could return A.length if target is greater than A[A.length-1]. //actually this is the same as lower_bound in C++ STL. private static int firstGreaterEqual(int[] A, int target) { int low = 0, high = A.length; while (low < high) { int mid = low + ((high - low) >> 1); //low <= mid < high if (A[mid] < target) { low = mid + 1; } else { //should not be mid-1 when A[mid]==target. //could be mid even if A[mid]>target because mid<high. high = mid; } } return low; } }
发表于 2017-03-12 15:02:39
回复(0)
问题信息
难度：
11条回答
49收藏
31613浏览
通过挑战的用户
查看代码-
2023-02-15 23:19:52
-
2023-02-13 17:59:34 -
2022-09-15 14:38:01 -
2022-08-24 10:54:27
-
2022-08-20 16:48:53
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
