Shinkai005

V1

2022/02/12阅读:43主题:红绯

# 【leetcode】35. 搜索插入位置

【leetcode】35. 搜索插入位置

image-20220212085245101
image-20220212085245101

题目描述

image-20211221212200080
image-20211221212200080

题目思路

O(logn)看到这个我就想到了二分查找.

那么具体怎么把二分查找应用到这道题往下看

个人题解

我把注解写到代码上,这样刷的快一些.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

var searchInsert = function (nums, target{
  // 这里写在Array原型上,是因为之前写过直接复制过来了.
    Array.prototype.binarySearch = function (item{
        let low = 0;
        let high = this.length - 1;
        while (low <= high) {
            const mid = Math.floor((low + high) / 2);// 1
            const element = this[mid];//3
            if (element < item) {// 3 和 2
                low = mid + 1;
            } else if (element > item) {//3>2
                high = mid - 1// 0
            } else {
                return mid;
            }
        }
        return low;//0
    }

    const res = nums.binarySearch(target);//[1,3,5,6] 2
    return res;
}

解释下为什么返回low,

因为二分法细分,最后一定会划分到 当前数

比如: 2的前后,

  • low就是0 high就是1
  • 下一步,low不变,high-1
  • 下一步low和high相等,返回low即可.

为什么不返回high?

  • 如果返回high,最后一步可能为-1 并且结果有时会小1(自己验证下什么情况 )

其他题解验证

看了一下其他答案大多也是用二分查找.

下面是官方题解,多使用一个ans变量.

秉着越少越好越短越好...我倾向自己的.

var searchInsert = function(nums, target{
    const n = nums.length;
    let left = 0, right = n - 1, ans = n;
    while (left <= right) {
        let mid = ((right - left) >> 1) + left;//这个位运算和/2取整数一样.前面检测过,现代浏览器处理api甚至比位运算更快.建议用Math.floor()
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
};

官方的ans没别的作用...语义化更好一点.

总结优化

没有

时间复杂度(time complexity)

O(logn) 二分法的时间复杂度

空间复杂度(space complexity)

O(1) 没有用数据结构,也没什么线性增长的变量.

分类:

前端

标签:

JavaScript

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai