14 - 搜索插入位置

题目

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

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5 输出: 2

示例 2:

输入: [1,3,5,6], 2 输出: 1

示例 3:

输入: [1,3,5,6], 7 输出: 4

示例 4:

输入: [1,3,5,6], 0 输出: 0

解答

感觉和two sum差不多,可以用哈希表和两分法

暴力解法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  if (nums[0] > target) {
    return 0;
  }
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return nums.length;
};

Runtime: 52 ms, faster than 85.47% of JavaScript online submissions for Search Insert Position.

Memory Usage: 34.3 MB, less than 41.45% of JavaScript online submissions for Search Insert Position.

双指针

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  if (nums[0] > target) {
    return 0;
  } else if (nums[nums.length - 1] < target) {
    return nums.length;
  }
  let start = 0;
  end = nums.length - 1;
  while (start <= end) {
    let mid = Math.round((start + end) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return start;
};

Runtime: 76 ms, faster than 5.48% of JavaScript online submissions forSearch Insert Position.

Memory Usage: 33.9 MB, less than 59.44% of JavaScript online submissions for Search Insert Position.

这运行时间简直惊呆了。。。

二分法

作者:liweiwei1419

链接:https://leetcode-cn.com/problems/two-sum/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/

这个liweiwei大佬可太厉害了,我刷题就知道这一题一地的解法,这个大佬还能抽象出模版,可以说是非常佩服了。

var searchInsert = function(nums, target) {
  let left = 0;
  right = nums.length - 1;
  while (left <= right) {
    let mid = Math.round((left + right) / 2);
    if (target === nums[mid]) {
      return mid;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
};

Runtime: 64 ms, faster than 22.58% of JavaScript online submissions for Search Insert Position.

Memory Usage: 33.7 MB, less than 98.01% of JavaScript online submissions for Search Insert Position.

基于这篇文章对这个二分法的优化:

var searchInsert = function(nums, target) {
  const length = nums.length;
  if (nums[length - 1] < target) {
    return length;
  } else if (length === 0) {
    return 0;
  }
  let left = 0;
  right = length - 1;
  while (left < right) {
    let mid = (left + right) >>> 1;
    if (target > nums[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return right;
};

Runtime: 52 ms, faster than 83.92% of JavaScript online submissions for Search Insert Position.

Memory Usage: 33.9 MB, less than 67.81% of JavaScript online submissions for Search Insert Position.

OK,那么究竟优化了哪些地方呢?

  • 前7行增加了边界判断

  • while的判断条件变成了小于号

之前的等号,leftright是不一样的值,那么还需要费神试出来究竟用哪个。

这里改成小于号,跳出while后,leftright都是一样的,可以再做判断等操作。

  • 11行用了一个很装逼的无符号右移

结果相当于Math.floor((left + right) / 2)。而且leftright必须是正数。

那为什么要这么写呢?

原先的(left + right) / 2,如果leftright都很大的情况下,加和可能超过最大安全数,导致结果不精确。

当然可以改成left + (right - left) / 2,不过如果right很大,而left很小,也会溢出。

>>>,不怕溢出,简单快捷,就是可读性差了点。

  • if的判断条件变成了两个

原先每次都要判断一下,万一nums[mid]就是结果了呢?

其实nums[mid]能命中结果的情况很罕见,每次循环都校验一下有没有命中,就好像每次出门买张彩票,不值得。

等二分结束出结果,再拿着结果做校验,是一个整体更加高效的行为。

关于死循环

我理解死循环的触发条件是这样:

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

比如算mid除以2得到2.5,那么可以取上界变3,如Math.round();也可以取下界变成2,如Math.floor()>>>

if循环中,如果nums[mid]小于了target,那么结论不可能是这个mid了。因此下一轮的left可以跳过这个mid,变成mid + 1

if对应的else,是nums[mid]大于等于了target,因此right对应的nums[right]有可能是target,就用right = mid保留。

因此,如果mid的计算取上边界,mid就可能等于right。这样就会进入else的死循环,right始终等于mid

为了避免这个问题,只要mid的边界选取和if的判断条件一致就行了。mid取下边界,if判断小于target

强烈建议看原文,我这个是非常简略了。

Last updated

Was this helpful?