34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
思路:二分法
这题和 leetcode 剑指 Offer 53 - I. 在排序数组中查找数字 I 的实现思路很像,都是查找 taret 的左右边界,
在二分查找法中使用 if(target >= nums[i]) left = mid + 1;可以找到第一个大于target的元素的位置。
其中该方法查找 target 的右边界,复用该函数查找 (target-1)的右边界即是 target 的左边界,右边界所指元素是第一个大于target元素,左边界所指元素是第一个大于 (target-1)的元素,
- 如果target存在的话,则因为左边界指向target的首次出现的值,右边界指向的是第一个大于 target 的元素的位置,所以target的位置范围为 [leftBorder, rightBorder - 1];
- 如果 target 不存在的话,右边界指向的是第一个大于target 的元素的位置,左边界指向的是第一个大于 (target -1) 的元素,本来应该指向target的,当时因为target 不存在,所以也指向了第一个大于target 的元素,所以此时 左右边界相等,leftBorder == rightBorder。
1 class Solution { 2 3 // 获取在nums数组第一个大于等于 target 的元素下标 4 public int getRightBorder(int[] nums, int target){ 5 int left = 0, right = nums.length - 1; 6 int mid = 0; 7 while(left <= right){ 8 mid = (left + right) / 2; 9 if(target >= nums[mid]){ 10 left = mid + 1; 11 }else{ 12 right = mid - 1; 13 } 14 } 15 return left; 16 } 17 18 public int[] searchRange(int[] nums, int target) { 19 if(nums == null || nums.length == 0){ 20 return new int[]{-1, -1}; 21 } 22 23 int leftBorder = getRightBorder(nums, target - 1); 24 int rightBorder = getRightBorder(nums, target); 25 if(leftBorder == rightBorder){ // 左右下标相等则说明该数不存在 26 return new int[]{-1, -1}; 27 } 28 return new int[]{leftBorder , rightBorder - 1}; 29 } 30 }leetcode 执行用时:0 ms > 100.00%, 内存消耗:41.9 MB > 69.63%
复杂度分析:
时间复杂度:O(logn)。使用二分法查找了 target 的左右边界,所以时间复杂度为O(logn)。
空间复杂度:O(1)。只使用了常数个大小的变量空间,所以空间复杂度为O(n)。