题目地址(34. 在排序数组中查找元素的第一个和最后一个位置)

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目描述

  1. 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
  3. 如果数组中不存在目标值 target，返回 [-1, -1]。
  5. 进阶：
  7. 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
  11. 示例 1：
  13. 输入：nums = [5,7,7,8,8,10], target = 8
  14. 输出：[3,4]
  16. 示例 2：
  18. 输入：nums = [5,7,7,8,8,10], target = 6
  19. 输出：[-1,-1]
  21. 示例 3：
  23. 输入：nums = [], target = 0
  24. 输出：[-1,-1]
  28. 提示：
  30. 0 <= nums.length <= 105
  31. -109 <= nums[i] <= 109
  32. nums 是一个非递减数组
  33. -109 <= target <= 109

前置知识

  • 二分查找

公司

  • 暂无

思路

先把取得边界的情况分为三种

  1. t在边界的左边或者右边
  2. t在边界中间 但是并没有在数组中
  3. t在数组中

针对这3种情况 需要求出数组的左边界和右边界 因为我比较菜 所以将左右边界分开求

关键点


代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.     public int[] searchRange(int[] nums, int target) {
  4.         int leftBorder = getLeftBorder(nums,target);//调用方法 返回左右边界的值
  5.         int rightBorder = getRightBorder(nums,target);
  6.         //情况一 左右边界的值都是初始化的值 并没有在区间内 如果有其中一个数字大于边界 那么他的其中一个边界值将未定义
  7.         if(leftBorder==-2||rightBorder==-2){
  8.             return new int[]{-1,-1};
  9.         }
  10.         //情况三 左右边界中有值
  11.         if(rightBorder - leftBorder >1){
  12.             return new int[]{leftBorder+1,rightBorder-1};
  13.         }
  14.         //情况二 在区间内 但是并无值
  15.         return new int[]{-1,-1};
  17.     }
  18.     public int getRightBorder(int[] nums , int target){
  19.         int begin = 0, end = nums.length - 1, rightBorder = -2; //初始化未标记的值
  20.         while (begin <= end) {
  21.             int mid = (begin + end) / 2;
  22.             if (nums[mid] > target) {
  23.                 end = mid - 1;// target 在左区间，所以[left, middle - 1]
  24.             } else {// 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
  25.                 begin = mid + 1;
  26.                 rightBorder = begin;
  27.             }
  28.         }
  29.         return rightBorder;
  30.     }
  31.     public int getLeftBorder(int[] nums , int target){
  32.         int begin = 0, end = nums.length - 1, leftBorder = -2;
  33.         while (begin <= end) {
  34.             int mid = (begin + end) / 2;
  35.             if (nums[mid] >= target) {// 寻找左边界，就要在nums[middle] == target的时候更新right
  36.                 end = mid - 1;
  37.                 leftBorder = end;
  38.             } else {
  39.                 begin = mid + 1;
  40.             }
  41.         }
  42.         return leftBorder;
  43.     }
  44. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：34. 在排序数组中查找元素的第一个和最后一个位置 - 图1#card=math&code=O%28logn%29&id=SbDil)
  • 空间复杂度：34. 在排序数组中查找元素的第一个和最后一个位置 - 图2#card=math&code=O%28n%29&id=zS0vO)