跳到主要内容

3 篇博文 含有标签「BS」

查看所有标签

力扣35-搜索插入位置[二分法]

· 阅读需 4 分钟
Yana Ching
Yana Ching
Front End Engineer

原题​

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。


示例 1:

> 输入: nums = [1,3,5,6], target = 5
> 输出: 2

示例 2:

> 输入: nums = [1,3,5,6], target = 2
> 输出: 1

示例 3:

> 输入: nums = [1,3,5,6], target = 7
> 输出: 4
提示
  • 1 <= nums.length <= 10⁴
  • -10⁴ <= nums[i] <= 10⁴
  • nums 为 无重复元素 的 升序 排列数组
  • -10⁴ <= target <= 10⁴

解题思路​

已知

  • 有序数组
  • 目标值 target

求

  • 若有 target，返回索引
  • 若无 target 返回顺序插入位置（right 位置）

空状态处理

  • 空数组，返回 0

解题过程​

  1. 初始化左右指针：left = 0, right = len(nums) - 1
    • （假设区间为 [l, r] 左右均闭合区间，结束外层循环时: l > r，当 target 比 l 小的时候，l 指向数组头；当 target < r 时，l 指向数组尾）
    • （假设区间为 [l, r) 左闭右开区间，结束外层循环时: l == r，直接返回 r 或者 l 都行 ）
  2. 空数组，返回 0
  3. 二分查找 target
    • 找到匹配的 target，返回 target 索引
    • 找不到匹配的 target，返回 right 指针位置

复杂度​

代码​

[l,r]​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  // [l, r]
  const n = nums.length
  let l = 0
  let r = n - 1
  // l <= r 条件，循环结束的时候 r > l,此时 r 为左边界，适合处理插入尾部的操作和空数组的情况
  // l < r 条件，循环结束的时候 r == l,此时直接返回即可
  while (l <= r) {
    mid = (l + r) >>> 1
    if (target === nums[mid]) {
      return mid
    } else if (target > nums[mid]) {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }
  return r + 1
}

[l,r)​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  // [l, r]
  const n = nums.length
  let l = 0
  let r = n
  // l <= r 条件，循环结束的时候 r > l,此时 r 为左边界，适合处理插入尾部的操作和空数组的情况
  // l < r 条件，循环结束的时候 r == l,此时直接返回即可
  while (l < r) {
    mid = (l + r) >>> 1
    if (target === nums[mid]) {
      return mid
    } else if (target > nums[mid]) {
      l = mid + 1
    } else {
      r = mid
    }
  }
  return r
  // return l 都是可以的
}

力扣34-在排序数组中查找元素的第一个和最后一个位置[二分法]

· 阅读需 5 分钟
Yana Ching
Yana Ching
Front End Engineer

原题​

给你一个按照非递减顺序排列的整数数组 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] :::tip
提示

  • 0 <= nums.length <= 10⁵

  • -10⁹ <= nums[i] <= 10⁹

  • nums 是一个非递减数组

  • -10⁹ <= target <= 10⁹

解题思路​

已知：

  1. 数组有序 - 定位 二分法
  2. nums
  3. target 值
  4. 有可能有重复元素

求：

  1. target 出现的第一个出现的位置
  2. target 出现的最后一个出现位置

寻找最左：

  1. 找到 mid 符合 target 之后，更新 LBoder 为 mid
  2. 将 r 移动到 mid 左边，寻找更左侧的 target
  3. 有就继续收缩，没有直接返回 -1

寻找最右：

  1. 找到 mid 符合 target 之后，更新 RBoder 为 mid
  2. 将 l 移动到 mid 右边，寻找更右侧的 target
  3. 有就继续收缩，没有直接返回 -1

明确隐藏条件：

  1. 若找不到 first，那么 last 也是不存在，因此首次判断 first 存在与否再决定是否寻找 last
  2. 当能找到 first 时，last 最小也只能是 first，不会出现 -1
  3. 检查空数组，空数组直接返回 [-1, -1]

解题过程​

  1. 初始化左右指针：left = 0, right = len(nums) - 1
  2. 二分查找第一个位置
    • 如果找到匹配的 target，将 right 指针移到中点的左侧继续查找，直到锁定第一个出现的 target。
  3. 二分查找最后一个位置
    • 如果找到匹配的 target，将 left 指针移到中点的右侧继续查找，直到锁定最后一个出现的 target。
  4. 返回结果：如果没有找到目标值，返回 [-1, -1]

复杂度​

  • 时间复杂度: O(logN)

  • 空间复杂度: O(1)

代码​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // 直接检查空数组
  const n = nums.length
  if (n === 0) return [-1, -1]

  function getFirst(nums, target, n) {
    // [l, r]
    let l = 0
    let r = n - 1
    let first = -1
    while (l <= r) {
      const mid = (l + r) >>> 1
      // 找到 target 位置后更新 first 位置，收缩右边界，继续向mid左边寻找是否有更左值
      if (target === nums[mid]) {
        first = mid
        r = mid - 1
      } else if (target > nums[mid]) {
        l = mid + 1
      } else {
        r = mid - 1
      }
    }
    return first
  }

  function getLast(nums, target, n) {
    // [l, r]
    let l = 0
    let r = n - 1
    let last = -1
    while (l <= r) {
      const mid = (l + r) >>> 1
      // 找到 target 位置后更新 last 位置，收缩左边界，继续向mid右边寻找是否有更右值
      if (target === nums[mid]) {
        last = mid
        l = mid + 1
      } else if (target > nums[mid]) {
        l = mid + 1
      } else {
        r = mid - 1
      }
    }
    return last
  }
  let first = getFirst(nums, target, n)
  // 如果找不到第一个位置，说明数组中没有这个元素，那么最后一个位置也是找不到的
  // 循环条件上理解则是 一旦 left 为 -1了，在循环条件 left <= right这个上， right也只能是 -1 了
  if (first === -1) return [-1, -1]
  // 一旦能够找到第一个位置，那么 last 最小也只能是 first
  // 循环条件上理解则是 一旦 left > 0 了，在循环条件 left <= right这个上， right也只能是 > 0 了
  let last = getLast(nums, target, n)
  return [first, last]
}