数学建模社区-数学中国
标题:
34. 在排序数组中查找元素的第一个和最后一个位置
[打印本页]
作者:
杨利霞
时间:
2022-9-5 16:45
标题:
34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
! r* j2 Z, f; C- ?5 Y1 d
难度中等
& W# F8 A, S& }
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
0 Z( q5 W! E0 x2 y: m
如果数组中不存在目标值 target，返回 [-1, -1]。
0 N5 F! M( v2 v1 S) B2 `. U
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
$ o" ?. d/ x, o/ T/ z2 K' k
+ A# E, P* s- }) A
示例 1：
: i! _3 A2 {" D1 |; ^. X+ }
输入：nums = [5,7,7,8,8,10], target = 8
# b3 p p! T, L
输出：[3,4]
?) ]6 {. {: i& j5 n
示例 2：
% I6 V9 q+ S# ~# c+ P) R
输入：nums = [5,7,7,8,8,10], target = 6
* m; T$ d5 z0 |- `' n
输出：[-1,-1]
8 o( Q6 Y# R; y% W6 t+ L6 d
示例 3：
+ T3 m& s9 q& W+ v' |
输入：nums = [], target = 0
& S& Y8 L% q- U; O6 c8 T% w* x' e: b
输出：[-1,-1]
6 S" l7 C: k, O9 s
1
M2 I! n# S: m: U, A3 Y$ {* n- M, I
2
6 a V @/ d% U. N( a c: x" W5 J( v6 C
3
/ p) `; K+ g s( S. v* ^
4
8 T6 C! D, T# C1 t) T7 H
5
3 ]/ f* _- U+ K0 t0 |1 @1 y( f
6
0 {. Z% X9 C& t* L9 q+ e. r. r
7
" d" @$ g' H4 Z# y/ |# f
8
; Z! ]: y) d% o$ ^8 l' s
9
+ ~9 e- D" L7 x9 h! u5 Z7 a
提示：
+ q$ J2 e4 j* i# d- K1 X
$ t f' q# l5 [7 ~8 u; r
0 <= nums.length <= 10(5)
2 L$ w! M2 D, j3 J& V( f' W
-10(9) <= nums[i] <= 10(9)
4 C& ?; O A7 o! h0 l
nums 是一个非递减数组
1 R# U( ?# Y) Q' f) ^ D9 l
-10(9) <= target <= 10(9)
" `: H) X, X( C& p. g6 A6 P2 T
思路
- I, q( O; Z) `/ J
关键步骤，与二分查找不同
: W/ L7 ?) V& u8 e: M' {
if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
* k; i3 x0 ^" U* c- |* E
target==nums[mid]时，不结束循环，继续进入
/ u$ g3 A$ Q1 @% S5 }
两个if可以同时进入，寻找界限
* u6 T9 u# Z; d* l& P' w
设置限制，防止mid-1,mid+1越界
$ G& W2 k# i* w K r: o% ~
代码
6 S3 i5 a0 x* j$ \
class Solution {
3 b5 \$ S8 u/ O5 R S- l
public:
4 e# ^5 v7 \) t# j& c: u9 V
int left=-1,right=-1;
o, m+ q6 H O3 L1 o$ O2 W; ]
vector<int> searchRange(vector<int>& nums, int target) {
6 G; E) k7 R( Y% ?; m+ o( Z
if(nums.size()==0) return vector<int>{-1,-1};
% W" x& P" _9 y: f, L
binary_search(nums,target,0,nums.size());
5 |# n/ c+ z. x
return vector<int>{left,right};
4 o j1 p+ \- \5 I% a: \+ Z
}
3 b: p# U) f1 x2 Z0 W
void binary_search(vector<int>& nums,int target,int l ,int r){
0 a& h( m1 ~+ v' I3 [$ X/ v
int mid=(r-l)/2+l;
, [! A/ i: z( y$ W
//printf("%d-%d\n",l,r);
& m8 i; H s( t: g. `
if(target==nums[mid]){
& f& f3 X. X6 `9 r' D
if(left>mid||left<0) left=mid;
( K7 y8 _; {; Z* ^8 q& F; W- z
if(right<mid||right<0) right=mid;
5 y) n# E0 {2 ?( N! _. F& h
}
6 h: [2 m+ j0 K& P0 A% b
if(l>=r) return;
/ |1 q- z/ O% _9 \" @6 l2 J8 `
if(target<=nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
2 [8 X- }: {4 e
if(target>=nums[mid]&&mid+1<nums.size()) binary_search(nums,target,mid+1,r);
' q2 W* k+ p; I0 G/ L
}
8 L% r2 e1 u2 |; j0 w( U# d( O
};
^/ S* q$ D$ G; F
" U2 m1 y! S, l9 Q
————————————————
+ m: G8 F' Q K5 I
版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! m& x& [, t3 S- H) B* t
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832
6 G' S; o% v* e; H8 x$ M
) U* K3 j5 q( ?$ w+ u! @( R
! E+ _0 _9 a: i% }8 v
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5