[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)


相关推荐

  • 任意角和弧度制[通俗易懂]

    任意角和弧度制[通俗易懂]1importmath23PI=math.pi45defshow():6print(7'小主,(* ̄︶ ̄),请选择你需要的功能:\n'8'\t\0

  • 网关 gateway_gateway网关集群

    网关 gateway_gateway网关集群GateWay网关管理GateWayCloud全家桶中有个很重要的组件就是网关,在1.x版本中都是采用的Zuul网关;但在2.x版本中,zuul的升级一直跳票,SpringCloud最后自己研发了一个网关替代Zuul,那就是SpringCloudGatewayGateway是在Spring生态系统之上构建的API网关服务,基于Spring5,SpringBoot2和ProjectReactor等技术。Gateway旨在提供一种简单而有效的方式来对API进行路由,以及提供一些强大的过滤

    2022年10月11日
  • 查看 CUDA cudnn 版本 & 测试 cuda 和 cudnn 有效性「建议收藏」

    查看 CUDA cudnn 版本 & 测试 cuda 和 cudnn 有效性「建议收藏」https://medium.com/@changrongko/nv-how-to-check-cuda-and-cudnn-version-e05aa21daf6ccuda版本cat/usr/local/cuda/version.txtcudnn版本cat/usr/local/cuda/include/cudnn.h|grepCUDNN_MAJOR-A2

  • 运用平面向量的坐标求内积_向量数量积推导过程

    运用平面向量的坐标求内积_向量数量积推导过程Forpersonaluseonlyinstudyandresearch;notforcommercialuse平面向量内积的坐标运算与距离公式德清乾元职高朱见锋【教材分析】:本课是在平面向量坐标运算、内积定义基础上学习的,主要知识是平面向量内积的坐标运算与平面内两点间的距离公式,是后面学习曲线方程的重要公式和推导依据,是进一步学习相关数学知识的重要基础。【教学目标】1.掌握平面向量内积的坐标表示…

  • Android下载apk异常java.net.SocketTimeoutException: timeout解决办法

    Android下载apk异常java.net.SocketTimeoutException: timeout解决办法1、问题实现下载apk的时候,抛出下面异常java.net.SocketTimeoutException:timeout2、分析很明显是socket超时了,由于我的wifi网络比较慢,设置的超时时间可能短了。在写入由GetRequestStream方法返回的流时,或在读取由GetResponseStream方法返回的流时,会用到ReadWriteTimeout属性,ReadWrite…

  • Windows10系统设置定时关机「建议收藏」

    Windows10系统设置定时关机「建议收藏」1.输入cmd运行命令提示符2.输入 shutdown–s–t3600   [注:3600为倒计时的秒数,此语句为系统在一小时后关机]/*shutdown命令的参数:shutdown-a 取消关机shutdown-s关机shutdown-f 强行关闭应用程序shutdown-m计算机名 控制远程计算机shutdown-i 显示“远程关机”图形用户界面,…

发表回复

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

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