leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置 (中等)
一、题目大意
标签: 查找
https://leetcode.cn/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
二、解题思路
给定一个增序的整数数组和一个值,查找该值第一次和最后一次出现的位置。使用二分查找找左右区间。lower_bound 返回的是开始的第一个满足条件的位置,upper_bound 返回的是第一个不满足条件的位置。所以当两个返回值相等的时候表示没有找到,找到了需要返回的是{left, right - 1}
三、解题方法
3.1 Java 实现
复制代码
四、总结小记
2022/5/26 二分查找 l 时间复杂度 O(logn)
版权声明: 本文为 InfoQ 作者【okokabcd】的原创文章。
原文链接:【http://xie.infoq.cn/article/306a32d128585a97a6a845515】。文章转载请联系作者。
评论