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

简介: LeetCode-34 在排序数组中查找元素的第一个和最后一个位置

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

题目描述

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

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

 

示例 1:

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

输出:[3,4]

示例 2:

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

输出:[-1,-1]

示例 3:

输入:nums = [], target = 0

输出:[-1,-1]

 

提示:

0 <= nums.length <= 105

-109 <= nums[i] <= 109

nums 是一个非递减数组

-109 <= target <= 109

 

解题思路

题目中限制时间复杂度为O(logn),那么很容易想到二分法,通过在二分法中更改等于时候的策略,就可以很简单求出上界和下界了,但是要注意边界样例。

代码展示

 

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int iLeft = 0, iRight = nums.size() - 1, iRetLeft = -1, iRetRight = -1;
        if(nums.size() == 0)
            return {iRetLeft, iRetRight};
        while(iLeft <= iRight)
        {
            int mid = (iLeft + iRight) >> 1;
            if(nums[mid] < target)
            {
                iLeft = mid + 1;
            }
            else
            {
                iRight = mid - 1;
            }
        }
        if(iLeft >= 0 && iLeft < nums.size() && nums[iLeft] == target)
            iRetLeft = iLeft;
        iLeft = 0, iRight = nums.size() - 1;
        while(iLeft <= iRight)
        {
            int mid = (iLeft + iRight) >> 1;
            if(nums[mid] <= target)
            {
                iLeft = mid + 1;
            }
            else
            {
                iRight = mid - 1;
            }
        }
        if(iRight >= 0 && iRight < nums.size() && nums[iRight] == target)
            iRetRight = iRight;
        return {iRetLeft, iRetRight};
    }
};

运行结果

 

相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
36 1
|
2月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
34 0
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
68 0
|
2月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
17 0
|
2月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
30 0
|
2月前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
32 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2