网站做交叉连接,网站建设依循的原则,wordpress装机主题,小程序免费制作题目
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [5,7,7,8,8,10], target 8
输出[3,4]
示例 2
输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]
示例 3
输入nums [], target 0
输出[-1,-1]
题解
class Solution {public int[] searchRange(int[] nums, int target) {int start lower_bounds(nums, target);if (start nums.length || nums[start] ! target) {//返回长度或者找不到目标值return new int[]{-1,-1};}//结束位置相当于满足条件target的前一个数int end lower_bounds(nums, target 1) - 1;return new int[]{start,end};}private int lower_bounds(int[] nums, int target) {//闭区间写法二分int n nums.length;int left 0;int right n - 1;while(left right) { //保证区间不为空 查找最后一个元素int mid left (right - left)/2;if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return left; //返回值也可以写right1}
}
