LeetCode 0034 - Find First and Last Position of Element in Sorted Array
# Hints
- 二分查找
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an array of integers sorted in ascending order, find the starting and ending position of a given value.
Your algorithm's runtime complexity must be in the order of .
If the target is not found in the array, return .
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
# 题意
给定一个长为 的非严格递增数组 ,给定一个整数 ,要求在 的时间内判断 在 内是否存在,如果存在则返回 表示其第一次和最后一次出现位置的下标,否则返回 。
# 题解
水题,直接二分查找即可。
细节问题:
- 注意特判查找失败的情况。
# AC代码
class Solution {
public:
vector<int> searchRange(vector<int> & nums, int target) {
// 二分查找
int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
// 特判
if (left > right) {
left = -1;
right = -1;
}
// 返回
return vector<int>({left, right});
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01