Leetcode如何搜索插入位置

小编给大家分享一下Leetcode如何搜索插入位置,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

题目描述:      
   
给定一个排序数组和一个目标值,在数组中找到目标值并返回其索引。若无目标值,则假设其插入到数组的对应位置,返回该位置的索引(假设数组无重复)    

   
例如:    
input:[1, 3, 5, 6] 5out:2
   

   
input:[1, 3, 5, 6] 2out:1
   
input:[1, 3, 5, 6] 7out:4
   


本文由“壹伴编辑器”提供技术支持

 

第一次尝试

数组:nums

目标值:target

从左到右遍历数组,当nums[i]==target时,返回此刻的索引值i。当nums[i]>target时说明数组里面无目标值,并且target应该就插入到此刻的i处,故索引值也是i

  • nums[i] == target:返回索引值 i

  • nums[i] > target:也是返回索引值 i

Leetcode如何搜索插入位置

Leetcode如何搜索插入位置

速度并不快Leetcode如何搜索插入位置Leetcode如何搜索插入位置Leetcode如何搜索插入位置

Leetcode如何搜索插入位置  



 


优化算法——二分查找


曾经有个小品:奇志和大兵去看病,医生让他做了心肝脾肺肾的全面检查,最后告诉他你就得了个感冒。虽然这是一个段子,但也映射出了一种治思维

二分法思想(减治):将【待搜索区域】划分为【含目标区域】和【不含目标区域】,不断的排除掉【不含目标区域】,最后剩下【含目标区域】

二分查找算法:

  • 利用三个游标:left、right、mid不断缩小区间

  • 在使用二分查找算法时要思考2个问题

    (1)返回 right 还是 left

    (2)区域边界如何设置


本文由“壹伴编辑器”提供技术支持

本题做法:

  • 设置left、right、mid三个参数

  • 循环条件为 while left<= right

  • 区间的划分方法:

    (1)mid=target时:返回mid

    (2)mid>target时:right = mid-1

    (3)mid<target时:left = mid+1

  • 此方法最后函数返回left(left始终对应target的位置即索引)

Leetcode如何搜索插入位置

Leetcode如何搜索插入位置

Leetcode如何搜索插入位置

Leetcode如何搜索插入位置  



 

Python内置函数方法

对于python,这是代码最简洁的一个方法——利用内置函数

  1. 先判断target是否存在于nums,存在直接返回index

  2. 若不在,则添加这个target进去nums,然后数组排序,返回target索引

Leetcode如何搜索插入位置

Leetcode如何搜索插入位置


本文由“壹伴编辑器”提供技术支持

其实也可以不判断是否在数组中,反正出现重复,返回索引也是返回的第一个

Leetcode如何搜索插入位置

Leetcode如何搜索插入位置

二分法小结

  • 三个游标:left、right、mid

  • 要确定好区间划分方法(left、right如何移动)

  • 确定好函数最后返回的是哪个值(通过演算)

以上是“Leetcode如何搜索插入位置”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注行业资讯频道!