LeetCode - 029 - 搜索插入位置(search-insert-position)

栏目: IT技术 · 发布时间: 5年前

内容简介:LeetCode - 029 - 搜索插入位置(search-insert-position)

Create by jsliang on 2019-06-10 08:54:47
Recently revised in 2019-06-10 13:07:28

一 目录

不折腾的前端,和咸鱼有什么区别

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | |  3.1 解法 - 暴力破解 | |  3.2 解法 - 二分法 |

二 前言

  • 难度:简单

  • 涉及知识:数组、二分查找

  • 题目地址:https://leetcode-cn.com/problems/search-insert-position/

  • 题目内容

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

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

  3. 示例 1:

  4. 输入: [1,3,5,6], 5

  5. 输出: 2

  6. 示例 2:

  7. 输入: [1,3,5,6], 2

  8. 输出: 1

  9. 示例 3:

  10. 输入: [1,3,5,6], 7

  11. 输出: 4

  12. 示例 4:

  13. 输入: [1,3,5,6], 0

  14. 输出: 0

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 讲解下使用 JavaScript 的解题思路。

3.1 解法 - 暴力破解

  • 解题代码

  1. var searchInsert = function(nums, target) {

  2. for (let i = 0; i < nums.length; i++) {

  3. if (nums[i] >= target) {

  4. return i;

  5. }

  6. }

  7. return nums.length;

  8. };

  • 执行测试

  1. nums: [1,3,5,6]

  2. target: 2

  3. return

  1. 1

  • LeetCode Submit

  1. Accepted

  2. 62/62 cases passed (88 ms)

  3. Your runtime beats 84.85 % of javascript submissions

  4. Your memory usage beats 56.95 % of javascript submissions (33.9 MB)

  • 解题思路

这道题通过遍历暴力破解的话,分 3 种情况判断:

  1. 如果 nums[i] 直到最终都小于 target,即 target 比整个数组中的元素都大,那么我们返回 nums.length(因为数组长度为 length-1,往后添加就是 length 位了)。

  2. 如果 nums[i]===target,那么直接返回这个索引。

  3. 如果 nums[i]>target,那么还是返回这个索引,例如 [1,3,5,6],我们判断 2,当遍历到 i===1 的时候, nums[2]===3,它大于 target2 这个数,所以我们需要往 [1,3] 直接插入,就是索引值为 1 了。

3.2 解法 - 二分法

  • 解题代码

  1. var searchInsert = function(nums, target) {

  2. let left = 0;

  3. let right = nums.length - 1;

  4. while (left <= right) {

  5. let middle = Math.round((left + right) / 2);

  6. if (target === nums[middle]) {

  7. return middle;

  8. } else if (target < nums[middle]) {

  9. right = middle - 1;

  10. } else if (target > nums[middle]) {

  11. left = middle + 1;

  12. }

  13. }

  14. return left;

  15. };

  • 执行测试

  1. nums: [1,3,5,6]

  2. target: 2

  3. return

  1. 1

  • LeetCode Submit

  1. Accepted

  2. 62/62 cases passed (72 ms)

  3. Your runtime beats 96.67 % of javascript submissions

  4. Your memory usage beats 47.82 % of javascript submissions (34.2 MB)

  • 知识点

  1. Math:JS 中的内置对象,具有数学常数和函数的属性和方法。 Math 详细介绍

  • 解题思路

首先,我们需要了解的是, 一个数/2,大概率返回的是小数,而我们的索引需要的是整数,所以我们通过 Math.round() 来四舍五入获取整数。

然后,就是 while 的逻辑判断:

  1. nums: [1,3,5,6]

  2. target: 2

LeetCode - 029 - 搜索插入位置(search-insert-position)

最后,我们需要知道的是,如果 target2,那么返回的 [left,right] 是: [1,0];如果 target4,那么返回的 [left,right][2,1]。因为循环结束的条件是 left>right,所以无疑 left 是更接近中间值的。


jsliang 广告推送:
也许小伙伴想了解下云服务器
或者小伙伴想买一台云服务器
或者小伙伴需要续费云服务器
欢迎点击 云服务器推广 查看!

LeetCode - 029 - 搜索插入位置(search-insert-position)
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。


以上所述就是小编给大家介绍的《LeetCode - 029 - 搜索插入位置(search-insert-position)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

领域驱动设计

领域驱动设计

[美] Eric Evans / 赵俐、盛海艳、刘霞 / 人民邮电出版社 / 2016-6-1 / 69

本书是领域驱动设计方面的经典之作,修订版更是对之前出版的中文版进行了全面的修订和完善。 全书围绕着设计和开发实践,结合若干真实的项目案例,向读者阐述如何在真实的软件开发中应用领域驱动设计。书中给出了领域驱动设计的系统化方法,并将人们普遍接受的一些实践综合到一起,融入了作者的见解和经验,展现了一些可扩展的设计新实践、已验证过的技术以及便于应对复杂领域的软件项目开发的基本原则。一起来看看 《领域驱动设计》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具