首页 > 代码库 > [Leetcode] Search for a Range
[Leetcode] Search for a Range
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].
Solution:
本题时间复杂度是O(log n)，暗示我们应该采用binary search的方法来做此题。
关键点在于有重复的元素，所以需要利用findMostLeft和findMostRight来找到起始和结束的位置。
1 public class Solution { 2 public int[] searchRange(int[] A, int target) { 3 int pos=binarySearch(A,target); 4 5 if(pos==-1){ 6 return new int[] {-1,-1}; 7 }else{ 8 int left=-1; 9 int right=-1;10 if(pos-1>=0&&A[pos]==A[pos-1]){11 left=findMostLeft(A,target,0,pos-1); 12 }13 else{14 left=pos; 15 }16 if(pos+1<=A.length-1&&A[pos]==A[pos+1]){17 right=findMostRight(A,target,pos+1,A.length-1);18 19 }else{20 right=pos;21 }22 return new int[] {left,right};23 }24 }25 public int findMostRight(int[] A,int target,int left,int right){26 27 while(left<=right){28 int mid=left+(right-left)/2;29 if(A[mid]==target){30 if(mid+1<=right&&A[mid]==A[mid+1])31 left=mid+1;32 else33 return mid;34 }else{35 right=mid-1;36 }37 }38 return -1;39 }40 public int findMostLeft(int[] A,int target,int left,int right){41 42 43 while(left<=right){44 int mid=left+(right-left)/2;45 if(A[mid]==target){46 if(mid-1>=left&&A[mid]==A[mid-1])47 right=mid-1;48 else49 return mid; 50 }else{51 left=mid+1;52 }53 mid=left+(right-left)/2;54 }55 return -1;56 }57 public int binarySearch(int[] A, int target){58 int left=0;59 int right=A.length-1;60 int mid=left+(right-left)/2;61 while(left<=right){62 63 64 if(A[mid]==target){65 66 return mid;67 }else if(A[mid]<target){68 left=mid+1;69 }else{70 right=mid-1;71 }72 mid=left+(right-left)/2;73 }74 return -1;75 }76 }
[Leetcode] Search for a Range
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。