今日军事新闻热点_企业网站的建设要注意哪些方面_网站模板商城_seo技术推广

解法一：先用二分查找找到最左边的target，再顺序寻找最右边的target。

class Solution {public int[] searchRange(int[] nums, int target) {int n=nums.length;if(n==0){return new int[]{-1, -1};}int left=0, right=n-1, ret = n;while(left<=right){int mid = (left+right)/2; //取中间或者中间左边的那个数if(nums[mid]>=target){ret=mid; // 取到最左边的targetright = mid-1;}else{left = mid+1;}}if(ret>=n){return new int[]{-1, -1};}if(nums[ret]==target){int i=ret+1;while(i<n){if(nums[i]!=target){break;}i++;}return new int[]{ret, i-1};}return new int[]{-1, -1};}
}

注意：

• int mid = (left+right)/2 每次都取中间或者中间左边的那个数
• ret=mid 每次都取到最左边的target
• if(n==0){ return new int[]{-1, -1}; } 应对 nums=[] 的情况
• if(ret>=n){ return new int[]{-1, -1}; } 应对 target 应该在n位置上的情况

错误原因：时间复杂度应该为O(logn+n)

解法二：传入参数bool，确定每次取最左边的target还是取最右边的target

class Solution {public int[] searchRange(int[] nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {return new int[]{leftIdx, rightIdx};} return new int[]{-1, -1};}public int binarySearch(int[] nums, int target, boolean lower) {int left = 0, right = nums.length - 1, ans = nums.length;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}
}