提供的爬取软件来源于:52pojie.cn@夜泉 免费下载使用

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

jsliang 飘飞的心灵 2019-06-11

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

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


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


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


精选留言

暂无...
吾爱破解论坛