Skip to main content

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回  [-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]

示例 3

输入：nums = [], target = 0
输出：[-1,-1]

答案​

对撞指针​

类似快速排序

时间复杂度为:logn

思路：

  1. 声明对撞指针 left/right

  2. 声明中位数 mid

  3. 根据二分法比较 target，找到对应下标 mid

    • while 循环条件： while (left <= right) {}
    • nums[mid]比较target
    • 找到对应下标 break
    • 未找到left = mid +1 / right = mid -1

  4. 不存在：if(left > right) return [-1, -1]

  5. 根据 mid 分别向两遍查找相同值的下标

    let i = mid
    let j = mid

    //向左尝试找相同的元素
    while(nums[i] === nums[i - 1]) i--;
    //向右尝试找相同的元素
    while(nums[j] === nums[j + 1]) j++;

  6. 返回[i,j]

var searchRange = function(nums, target) {
  let left = 0
  let right = nums.length - 1
  let mid // 找到目标

  // 根据二分法不target
  while (left <= right) {
    mid = parseInt((left + right) / 2);

    if (nums[mid] === target) break;

    if (nums[mid] > target) {
      right = mid - 1
    }else{
      left = mid + 1;
    }
  }

  if(left > right) return [-1, -1];

  let i = mid
  let j = mid

  //向左尝试找相同的元素
  while(nums[i] === nums[i - 1]) i--;
  //向右尝试找相同的元素
  while(nums[j] === nums[j + 1]) j++;

  return [i, j];
};

var nums = [5,7,7,8,8,10], target = 8
console.log(searchRange(nums,target))

暴力​

var searchRange = function(nums, target) {
  // 下标数组
  let result = []

  nums.forEach((item,index)=>{
    if(item === target){
      // 最大长度为2
      if(result.length === 2){
        result.pop()//把末尾弹出
        result.push(index)//更新
      }else{
        result.push(index)
      }

    }
  })

  // 判断结果长度
  if(result.length > 1){ // 直接返回
    return result
  }else if(result.length === 1){ // 仅一个
    result = [result[0],result[0]]
    return result
  }else{ // 没找到
    return [-1,-1]
  }
};

var nums = [5,7,7,8,8,10], target = 8
console.log(searchRange(nums,target))