数学建模社区-数学中国
标题:
34. 在排序数组中查找元素的第一个和最后一个位置
[打印本页]
作者:
杨利霞
时间:
2022-9-5 16:45
标题:
34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
8 M8 m, T8 c5 J* x
难度中等
5 y, G/ z0 E8 s' J
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
. U( I2 ]6 b# B: h/ a) o
如果数组中不存在目标值 target，返回 [-1, -1]。
& ~0 [+ z- d6 q
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
+ V! Y/ i7 H& M# u. Z" g0 n
# K1 H; }2 @2 X) p* P. j: W
示例 1：
+ N. i& V5 i& u) O* o$ g# l
输入：nums = [5,7,7,8,8,10], target = 8
' F$ m) G8 ] Z+ I1 v
输出：[3,4]
6 [ ?' R2 \+ s! d2 z! d6 W# j
示例 2：
( T: F& C1 Y5 u$ V/ w, b" X7 H
输入：nums = [5,7,7,8,8,10], target = 6
) x- N* R$ g7 g. B. I H& B6 V
输出：[-1,-1]
; T4 Z( W* @! [( I4 m% r( o2 i
示例 3：
7 [, r0 v1 F& ?
输入：nums = [], target = 0
0 }$ p# y# {4 V+ }
输出：[-1,-1]
7 N( G7 ]. `9 Z& y, \+ P
1
& z1 W" `. ~6 I+ l% @/ M/ B
2
" e9 a+ \( D+ n7 Q3 U% S
3
; b& n' o$ X, U3 X( X
4
7 E" E$ W- J! _6 ?9 C
5
2 J' e$ f) a4 T
6
3 K7 I. C( p" u1 { h @6 k) s
7
- h- t* d& U6 j: Q" N6 {7 u8 U# s; U
8
! \( q. h* J: _) `* w! u
9
& e6 Y6 K0 v! k( p3 Y0 f( o
提示：
% x N3 Y' G0 N. s' E
6 D+ c6 a% z" C
0 <= nums.length <= 10(5)
! p$ [. ~; H6 D0 G
-10(9) <= nums[i] <= 10(9)
, k% i7 }% W$ M0 o- U6 ~
nums 是一个非递减数组
' ?, K! E6 z8 \( X
-10(9) <= target <= 10(9)
' i' R# Y! K0 s4 m2 H, @
思路
5 o: ]2 m9 ]" ]7 ]! O
关键步骤，与二分查找不同
; [2 }/ Z5 I/ u, Q
if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
/ x; a3 ^: c+ s# U( P: b. L
target==nums[mid]时，不结束循环，继续进入
' O& T5 w/ o, y6 v* Q
两个if可以同时进入，寻找界限
8 O7 R' K0 r% D9 ?9 a5 x0 l' Z
设置限制，防止mid-1,mid+1越界
! \) x- O- ]. N/ R# ~
代码
9 u7 ^. t# w! w0 `, L' X$ m/ ]
class Solution {
' g3 I9 D4 [6 U- {3 B0 [
public:
) G# P8 x$ F, R, B' c, q
int left=-1,right=-1;
4 c0 M; l, u1 E4 Z$ N. B2 p
vector<int> searchRange(vector<int>& nums, int target) {
1 x7 }* j% t* w# X4 l* o. c0 O
if(nums.size()==0) return vector<int>{-1,-1};
* b+ w' y7 g8 k
binary_search(nums,target,0,nums.size());
0 B2 r/ P- o( Y: }
return vector<int>{left,right};
6 g8 Z! T* a( F: i& A D2 N
}
7 L, Q" r# t U. ~5 Y' M7 D
void binary_search(vector<int>& nums,int target,int l ,int r){
- B" c9 ]% _+ l4 \+ Y4 C
int mid=(r-l)/2+l;
: R+ a$ |( g3 {: t! y; N' V
//printf("%d-%d\n",l,r);
* Y5 p3 n; _: ^, s) b8 _; q8 y
if(target==nums[mid]){
1 `. v8 j4 |) Q! ^2 ?1 k4 A6 P+ [
if(left>mid||left<0) left=mid;
$ `0 A7 z. M, x: A! I
if(right<mid||right<0) right=mid;
/ d0 E- ]! Z- L' b2 x& e$ e0 ?
}
3 X3 d6 [6 [+ Y$ s( x ?! G
if(l>=r) return;
) T/ U* p4 ?! a9 X
if(target<=nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
$ C; p" @$ J; e$ Q
if(target>=nums[mid]&&mid+1<nums.size()) binary_search(nums,target,mid+1,r);
( }/ x: ^/ I/ g$ N
}
: O" v1 D% K6 D3 B* z# @: r( C
};
q# P) p6 K y
. k/ Y% f' H: M2 _" P" s" ~
————————————————
' v+ u" B: P* ~6 v
版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. G6 I9 |* ^7 m5 |( r& Z
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832
) D) Z" v+ M' N( X; F7 n
: A1 _. r; A6 f3 e( G
3 M9 b I- Y- D4 z/ `1 N; W. i
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5