数学建模社区-数学中国
标题:
34. 在排序数组中查找元素的第一个和最后一个位置
[打印本页]
作者:
杨利霞
时间:
2022-9-5 16:45
标题:
34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
3 y! G$ C$ I# r5 w
难度中等
0 R6 E& c% j$ W! J5 H6 Z- A0 Y
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
( X; G$ Z i; X: ?2 [' J
如果数组中不存在目标值 target，返回 [-1, -1]。
5 D( ^: O# E1 d3 l( y
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
6 {8 k/ n0 M; A
% U( L' X" Z6 b$ m* u& c
示例 1：
0 x! {+ E- ~, C% R5 t
输入：nums = [5,7,7,8,8,10], target = 8
& z( g, y: \3 k2 B& j
输出：[3,4]
2 t3 i$ A1 @& V! l
示例 2：
f% h2 a& ^( q O' T& t
输入：nums = [5,7,7,8,8,10], target = 6
% y1 c8 ~' h$ [3 W8 a4 h/ \
输出：[-1,-1]
/ e% @. n. J# T! ?+ e' k9 k: V
示例 3：
8 Y4 s& {+ f0 z; h
输入：nums = [], target = 0
9 u7 R* h: ]0 w" x" k( B
输出：[-1,-1]
7 X( G3 _6 X1 Z
1
1 c' o; l, c5 d- C7 @2 E
2
$ u' v: E' I0 \# N( G" Y, y
3
% H, u. ?# [$ E7 a# x0 R R
4
1 f4 f. D- a! G- d. o* C
5
. M5 N3 @4 j8 D8 N( Z, S* J, F! h2 H
6
) B7 R5 B, R2 k3 D8 y+ t+ v
7
6 P* w$ d4 O, _7 _) }
8
: ]& |; @4 H, W1 N& S: E
9
* _) y1 q7 C2 v* c9 Q) q2 D# G
提示：
& j! C5 @1 c0 a' x* ~" _. h/ H
5 i; V# {1 J9 e5 k+ O
0 <= nums.length <= 10(5)
3 H- v& p9 ]4 T9 I
-10(9) <= nums[i] <= 10(9)
8 S ?1 X% w% j; a4 k& {3 z
nums 是一个非递减数组
& ?4 m; E/ {7 i3 M" o
-10(9) <= target <= 10(9)
3 O7 O) s& ~) m" I
思路
4 e3 r9 S9 I" p" ^: p, {
关键步骤，与二分查找不同
- Z' x& N; e% W4 F" r2 P3 {7 Y! @+ I. ]" V
if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
) ^2 J8 H8 k# U e* T4 m3 P
target==nums[mid]时，不结束循环，继续进入
" z k5 Z( O$ y K: `6 z
两个if可以同时进入，寻找界限
* I# f2 ^+ f' L. I2 \
设置限制，防止mid-1,mid+1越界
& A+ [3 K2 l( H6 q, W) \2 O
代码
8 v8 ^6 a3 Q8 s
class Solution {
O$ |3 o5 U1 t _$ H3 r/ x
public:
+ v6 Q) B5 _, z$ G3 e: Z: m
int left=-1,right=-1;
. r; y, h/ w4 p% O7 K
vector<int> searchRange(vector<int>& nums, int target) {
# @( f" K+ [0 L$ Q6 o. ]' ?, [$ i
if(nums.size()==0) return vector<int>{-1,-1};
1 O5 T* T6 r: Y: S: ^- G: q8 [
binary_search(nums,target,0,nums.size());
9 ]1 y" Q; l' t
return vector<int>{left,right};
. {! [3 @1 i, @! a
}
5 ?' A I. u4 ]/ s; M
void binary_search(vector<int>& nums,int target,int l ,int r){
7 O# c3 m5 i& g
int mid=(r-l)/2+l;
3 X+ [6 S r' b( z: {9 a& h0 n! L
//printf("%d-%d\n",l,r);
( i9 M- P5 x" V& F; h8 x2 V
if(target==nums[mid]){
; W9 C: |9 p% Y' y: V' T; y- m
if(left>mid||left<0) left=mid;
+ b" r& r9 o# K T& O
if(right<mid||right<0) right=mid;
8 `9 B# n* }. \: P
}
8 P0 x% O6 u( U" L
if(l>=r) return;
9 c/ N7 l' L% p, v
if(target<=nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
" r* g! T" w. [+ g8 r5 h' h
if(target>=nums[mid]&&mid+1<nums.size()) binary_search(nums,target,mid+1,r);
) E9 w& B2 E& K
}
0 }, z: ` h* C
};
2 P. H& @0 j. N+ Q5 n
P. x- ]5 h j9 R. Q! Q
————————————————
0 ~6 |) H/ D8 z4 v7 o9 e
版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
; d+ R/ R. n8 k( B
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832
8 y/ ]$ f* `6 Z+ B, H- R0 h x
/ I/ M/ `3 }& C7 U1 N2 {
! B3 O/ p! T+ I* Y; N. |. g/ ~
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5