[leetcode]Search for a Range

[leetcode]Search for a Range

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

问题叙述性说明:

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order ofO(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].


基本思路:

此题能够用二分查找法解决。

假设数组中没有target,能够在O(lgn)时间完毕。

假设数组中有target,当发现target后,对前后的内容继续用二分法 查找这种位置pos 。

  1. 前面的pos须要满足 A[pos] < target && A[pos+1] == target. pos+1即是開始位置。
  2. 后面的pos须要满足 A[pos] > target && A[pos-1] == target . pos-1是结束位置。

代码:

vector<int> searchRange(int A[], int n, int target) {   //C++
        vector<int> result(2);
        
        int low = 0, high = n-1;
        int mid, begin = -1, end = -1;
        while(low <= high)
        {
            mid = (low+high)/2;
            if(A[mid] > target)
                high = mid - 1;
            else if(A[mid] < target)
                low = mid + 1;
            else 
            {
                    begin = mid;
                    end = mid;
                    
                    //get begin
                    if(low <= begin -1){
                        while((low <= begin-1) && !(A[low]<target && A[low+1] == target) )
                        {
                            mid = (low + begin-1)/2;
                            if(A[mid] < target)
                                low = mid+1;
                            else begin = mid;
                        }
                        if(A[low]<target && A[low+1] == target)
                            begin = low+1;
                    }
                    //get end
                    if(high >= end+1){
                        while((high >= end+1) &&!(A[high]>target && A[high-1] == target))
                        {
                            mid = (high + end +1)/2;
                            if(A[mid] > target)
                                high = mid - 1;
                            else end = mid;
                        }
                        if(A[high]>target && A[high-1] == target)
                            end = high - 1;
                    }
                    break;
                    
            }
        }
        result[0] = begin;
        result[1] = end;
        return result;
    }

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116862.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 【动态规划】01背包问题(通俗易懂,超基础讲解)[通俗易懂]

    【动态规划】01背包问题(通俗易懂,超基础讲解)[通俗易懂]问题描述有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8i(物品编号) 1 2 3 4 w(体积) 2 3 4 5 v(价值) 3 4 5 6 总…

  • python正方形螺旋线的绘制

    python正方形螺旋线的绘制多试错,反正又不要成本。importturtlea=1foriinrange(50):turtle.left(90)turtle.fd(a+1)turtle.left(90)

  • jdbc如何连接mysql数据库_sqlplus连接远程数据库

    jdbc如何连接mysql数据库_sqlplus连接远程数据库好多朋友遇到了在本地可以连接mysql数据库,而在jsp页面连接远程mysql数据库而连不上的问题,现总结以下:1.配置远程mysql数据库,使其允许远程tcp/ip连接,开放默认端口(3306) 或者设置为3309,2.创建用户,使其具有在任意HOST连接任意database的权限;3.在jdbc连接串中设置端口,如:jdbc:mysql://192.168.0.2:3309/ic

    2022年10月10日
  • JavaScript Array splice() 方法

    JavaScript Array splice() 方法语法array.splice(index,howmany,item1,…..,itemX)实例在位置2,添加新项目,并删除1个项目:varfruits=[“Banana”,”Orange”,”Apple”,”Mango”];fruits.splice(2,1,”Lemon”,”Kiwi”);在位置2,添加新项目varfruits=[“Banana”,”Orange”,”Apple”,”Mango”];fruits.s.

  • Kotlin与Java的异同(一)

    Kotlin与Java的异同(一)Kotlin简介Kotlin是一种针对Java平台的新编程语言。Kotlin简洁、安全、务实,并且专注于与Java代码的互操作性。它几乎可以用在现在Java使用的任何地方:服务端开发、Android应用等等。Kotlin可以很好地和所有现存的Java库和框架一起工作,而且性能和Java旗鼓相当。Kotlin特点:Kotlin是静态类型语言并支持类型推导,允许维护正确性与性能的同时保…

  • windows进程system占用CPU(电脑cpu过高怎么处理)

    自从升级到Win10系统后,经常发现任务管理器中的System进程占用了很高的CPU内存,这也导致多项应用程序无法正常运行,并且这个进程占用内存是没有上限,对于这种情况我们该如何处理呢?下面我们就一起来看看System占用CPU内存过高的解决方法。1、右键点击开始菜单,打开计算机管理页面;2、在计算机管理页面中打开计算机“服务”界面;3、在…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号