文档章节

【LeetCode】在排序数组中查找元素的第一个和最后一个位置

o
 osc_isezqdgg
发布于 2019/09/18 10:41
字数 359
阅读 3
收藏 0

精选30+云产品,助力企业轻松上云!>>>

【问题】给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-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]

【思路】在一个排序数组中查找某个元素的算法,我们很容易可以写出来寻找一个元素左边界的二分算法,即将target与mid相等时,将右边界r变为mid-1,向右移动即可!
那么怎么去查找某个元素的第一个和最后一个位置呢?很简单的思路,我们将左边界算法的查找目标target变化一下就可以了,第一次查找target,可以得到左边界的位置,第二次查找target+1,可能找到也可能找不到,但返回的都是最后位置+1的位置。

class Solution {
public:
     vector<int> searchRange(vector<int>& nums, int target) {
        int idx1 = lower_bound(nums, target);
        int idx2 = lower_bound(nums, target+1)-1;
        if (idx1 < nums.size() && nums[idx1] == target)
            return {idx1, idx2};
        else
            return {-1, -1};
     }

    int lower_bound(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l <= r) {
            int mid = l+(r-l)/2;
            if (nums[mid] < target)
                l = mid+1;
            else
                r = mid-1;
        }
        return l;
    }
};
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
LeetCode 面试题53 - I. 在排序数组中查找数字 I

我的LeetCode:https://leetcode-cn.com/u/ituring/ 我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 面试题53 - I. 在排序数组中查找数字 I 与以下题目相......

osc_auwur47t
05/23
4
0
[算法总结] 二分查找

本文首发于我的个人博客:尾尾部落 二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。 二分查...

繁著
2018/08/16
0
0
Leetcode 30-50题总结

LeetCode 31. 下一个排列 排列数规律,难 LeetCode 32. 最长有效括号 难 LeetCode 33. 搜索旋转排序数组 两次二分,第一次先找到旋转位置,第二次再有序数组里找,将两次二分合并成一个。 Le...

osc_8r37p3dx
06/19
6
0
LeetCode 面试题53 - I. 在排序数组中查找数字 I

我的LeetCode:https://leetcode-cn.com/u/ituring/ 我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 面试题53 - I. 在排序数组中查找数字 I 与以下题目相......

图灵的图,图灵的灵。
05/22
0
0
Leetcode 30-50题总结

LeetCode 31. 下一个排列 排列数规律,难 LeetCode 32. 最长有效括号 难 LeetCode 33. 搜索旋转排序数组 两次二分,第一次先找到旋转位置,第二次再有序数组里找,将两次二分合并成一个。 Le...

wwxy261
06/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【Nginx】实现负载均衡、限流、缓存、黑白名单和灰度发布,这是最全的一篇了!

写在前面 在《【高并发】面试官问我如何使用Nginx实现限流,我如此回答轻松拿到了Offer!》一文中,我们主要介绍了如何使用Nginx进行限流,以避免系统被大流量压垮。除此之外,Nginx还有很多...

osc_6l5fg87g
29分钟前
9
0
一小时完成后台开发:DjangoRestFramework开发实践

DjangoRestFramework开发实践 在这之前我写过一篇关于Django与Drf快速开发实践的博客,Django快速开发实践:Drf框架和xadmin配置指北,粗略说了一下Drf配置和基本使用,不过里面只是涉及到最...

osc_z2ru77w0
30分钟前
14
0
数据载入、存储及文件格式知识图谱-《利用Python进行数据分析》

所有内容整理自《利用Python进行数据分析》,使用MindMaster Pro 7.3制作,emmx格式,源文件已经上传Github,需要的同学转左上角自行下载或者右击保存图片。

osc_161difcz
32分钟前
8
0
Java异常

一、异常? java系统中将java.lang.Throwable类作为异常的最根类 [java.lang.Throwable是所有异常或错误的顶级类,可以处理任何异常] * java.lang.Throwable * |-----java.lang.Error:一般...

osc_o44vh5qb
33分钟前
23
0
(1)Linux系统中到底应该怎么理解系统的平均负载

每次发现系统变慢时,我们通常做的第一件事,就是执行 top 或者 uptime 命令,来了解系统的负载情况。比如像下面这样,我在命令行里输入了 uptime 命令,系统也随即给出了结果。 $ uptime...

osc_i5oyb1xr
34分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部