新郑龙湖网站建设,小叮当网站建设,小程序平台登录,qq在线网站代码34.给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1#xff1… 34.给你一个按照非递减顺序排列的整数数组 nums和一个目标值 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] 非递减数组求区间很容易想到的是两次二分查找找到左右边界。由于左右边界的找法几乎相同所以把题目转换一下只要找到 target 的右边界我们就知道了结束位置为右边界 - 1而开始位置我们只要知道 target - 1 的右边界即可因为是整数数组所以只要 target 在数组中存在那么刚刚大于 target - 1也就是右边界 的肯定是 target。这样的话我们只需要把二分查找右边界写成方法最终返回大致为 [solve(target-1),solve(target)-1] 即可。剩下的就是分析区间不存在的情况。首先数组没数肯定就直接返回了其次如果我能找到区间。那么可以肯定的是nums[开始位置] 一定是等于 target 的不是的话肯定也返回了。还有就是如果所有数都比 target 小那么起始位置会找到数组外面去所以二分查找返回的数组下标也应当合法。 public int[] searchRange(int[] nums, int target) {if(nums.length 0){return new int[]{-1,-1};}int first solve(nums,target-1);// 需要先判断 first 是否合法否则 nums[first] 可能直接数组越界了if(first nums.length || nums[first] ! target){return new int[]{-1,-1};}return new int[]{first,solve(nums,target)-1};}public int solve(int[] nums,int target){int left0,rightnums.length-1;while(leftright left 0 right nums.length-1){int mid (leftright)/2;// 这里用小于等于那么左边界就会不断右移直到找到大于 target 的第一个数// 所以这里的 left 最后就是 target 的右边界如果用小于就是左边界了if(nums[mid]target)leftmid1;else rightmid-1;}return left;}
