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

简介: 题目描述给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。进阶:你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

题目描述


给定一个按照升序排列的整数数组 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


解题思路


题目本身是非常简单的,就是二分查找,难点在于数组中可能有重复的元素,如何实现去重的逻辑,在找到了 target 之后先不要返回,此时从中间往两边去搜索是否有重复的元素,然后移动数组的下标即可完成去重。


代码实现


class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid;
                right = mid;
                while (left > 0 && nums[left] == nums[left - 1]) left --;
                while (right < nums.length - 1 && nums[right] == nums[right + 1]) right ++;
                return new int[]{left, right};
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int[]{-1, -1};
    }
}


执行结果


相关文章
|
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