第三十五题 35. 搜索插入位置
2021/9/16 23:06:28
本文主要是介绍第三十五题 35. 搜索插入位置,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
35. 搜索插入位置
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
示例 4
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5
输入: nums = [1], target = 0
输出: 0
提示:
- 1 <= nums.length <= 104
- -10 ^4 <= nums[i] <= 10 ^4 nums 为无重复元素的升序排列数组
- -10 ^4 <= target <= 10 ^4
思路
请必须使用时间复杂度为 O(log n) 的算法。 且 nums 为重复元素的升序排列数组 这些关键字很明显在暗示我们使用 二分查找
基本模板
- 初始化 left 在 索引 0 位置
- 初始化 right 在 nums.length - 1 位置
- index 位于 left 和 right 之间的中心位置 即(left+right )/ 2 js版本中 (left + right)>>> 1 位运算结果一致
- 当查找到的元素过小 左指针右移至中心的后一位 left = index + 1
- 当查找到的元素过大 右指针右移至中心的前一位 right = index - 1
注意:当 target 不在数组里面,需要确定 target 能够按照升序放在 nums 数组的位置
所以需要做多一个步骤 当查找到的元素过小时 需要给 index 加上 1 表示如果没找到 那就放在比它值小元素的后面一位
代码
/** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function(nums, target) { let left = 0; let right = nums.length - 1; let index = 0; while(left <= right){ //取中间位置 index = (left + right)>>>1; //搜索值比目标值小 index 指针右移 if(nums[index] < target){ left = index + 1; // 以防万一 可能nums不存在 目标值 就把它放后一位 index = index + 1; } //搜索值比目标值大 index 指针左移 else if(nums[index] > target){ right = index - 1; } //找到 搜索值就是目标值 else if(nums[index]===target){ return index; } } return index; };
这篇关于第三十五题 35. 搜索插入位置的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!