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
速度并不快
优化算法——二分查找
曾经有个小品:奇志和大兵去看病,医生让他做了心肝脾肺肾的全面检查,最后告诉他你就得了个感冒。虽然这是一个段子,但也映射出了一种分治思维
二分法思想(减治):将【待搜索区域】划分为【含目标区域】和【不含目标区域】,不断的排除掉【不含目标区域】,最后剩下【含目标区域】
二分查找算法:
利用三个游标: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
此方法最后函数返回left(left始终对应target的位置即索引)
Python内置函数方法
对于python,这是代码最简洁的一个方法——利用内置函数
先判断target是否存在于nums,存在直接返回index
若不在,则添加这个target进去nums,然后数组排序,返回target索引
本文由“壹伴编辑器”提供技术支持
其实也可以不判断是否在数组中,反正出现重复,返回索引也是返回的第一个
二分法小结
三个游标:left、right、mid
要确定好区间划分方法(left、right如何移动)
确定好函数最后返回的是哪个值(通过演算)
以上是“Leetcode如何搜索插入位置”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!
文章题目:Leetcode如何搜索插入位置
分享路径:http://scyanting.com/article/jspcoi.html