码迷,mamicode.com
                                                                              首页 > 编程语言 > 详细

                                                                              LeetCode第三十四题-寻找数组中?#26434;?#30446;标值的首尾索引

                                                                              时间:2019-05-09 13:54:52      阅读:32      评论:0      收藏:0      [点我收藏+]

                                                                              标签:class   tar   ima   二进制   状态   刷题   .so   索引   运行时   

                                                                              Find First and Last Position of Element in Sorted Array

                                                                              问题简介:给定按升序排序的整数数组,找到给定目标值的起始位置和结束位置.

                                                                              注:

                                                                              1.算法的运行时复杂度必须为O(log n)

                                                                              2.如果在数组中找不到目标,则返回[-1,-1]

                                                                              举例:

                                                                              1:

                                                                              输入: nums = [5,7,7,8,8,10], target = 8

                                                                              输出: [3,4]

                                                                              2:

                                                                              输入: nums = [5,7,7,8,8,10], target = 6

                                                                              输出: [-1,-1]

                                                                              解法一:

                                                                              可?#28304;?#22836;遍历,第一次找到目标值的即第一个索引,再倒序遍历,寻找目标值

                                                                              技术图片

                                                                              解法二:

                                                                              我们也可?#26434;?#25913;进的二进?#35780;?#20570;,定义一个方法来分别求数组中第一个和最后一个与target相同值的索引,其中left是状态值,当left=true时,代表这个方法时寻找第一个索引值,false即最后一个索引值

                                                                              技术图片

                                                                              复杂度分析:

                                                                              时间复杂度:o(log10(n))

                                                                              空间复杂度:o(1)

                                                                              小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海

                                                                              技术图片

                                                                              LeetCode第三十四题-寻找数组中?#26434;?#30446;标值的首尾索引

                                                                              标签:class   tar   ima   二进制   状态   刷题   .so   索引   运行时   

                                                                              原文地址:https://www.cnblogs.com/lalalaczq/p/10837699.html

                                                                              (0)
                                                                              (0)
                                                                                 
                                                                              举报
                                                                              评论 一句话评论(0
                                                                              0条  
                                                                              登录后才能评论!
                                                                              ? 2014 mamicode.com 版权所有 京ICP备13008772号-2
                                                                              迷上了代码!
                                                                              宁夏11选5开奖查询