数学建模社区-数学中国
标题:
34. 在排序数组中查找元素的第一个和最后一个位置
[打印本页]
作者:
杨利霞
时间:
2022-9-5 16:45
标题:
34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
' j2 F% t1 I) h1 @) t" y
难度中等
) q& u$ a0 c5 q5 X$ C& J
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
3 l. _3 [ A2 @% ~( H( l
如果数组中不存在目标值 target，返回 [-1, -1]。
9 C! X8 E+ o* j3 W# F. P( l
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
& I% A' }2 U$ C! W* d0 P g/ N$ L
% i. u8 K7 L( A# D* B3 D' E
示例 1：
, j: ^* C' d0 K6 B
输入：nums = [5,7,7,8,8,10], target = 8
8 o, i. @7 s/ b( w+ K
输出：[3,4]
1 D# N+ |2 t0 \9 k
示例 2：
1 ]" C( g( D: @: h9 q4 p' n4 R
输入：nums = [5,7,7,8,8,10], target = 6
1 t4 M" r+ K( x+ d& R2 ~: E; l
输出：[-1,-1]
4 y c ~/ g7 I0 w- p$ d2 i" }' `
示例 3：
9 J% [# |' r8 [ `9 s* i; N! Z
输入：nums = [], target = 0
3 s/ e" c$ J0 h7 @/ d0 K* E- d
输出：[-1,-1]
9 a/ l" _8 x2 g, H" Y) g
1
! H4 \2 ^% G. X J8 j
2
1 T) d/ b; \! t$ }- K _( ?
3
( M, f- X6 t: Y7 _& p, @
4
, Z! ]' L- m1 `) k7 [8 y. X
5
8 c% s. \) j9 U3 g# H! \# J2 ~
6
: q: M6 ?" ^0 t7 R0 Q; L
7
7 o6 P" a; P- L, f. N
8
% |3 c {) Y2 U6 @: l* t6 a5 X
9
; m# u8 [2 C h7 S' `1 B
提示：
* P* Z. ^# F. r5 m0 ]+ n+ J e
. A4 J1 E. f/ q: T
0 <= nums.length <= 10(5)
: Q, X9 l+ ]6 G* w
-10(9) <= nums[i] <= 10(9)
& l5 \! }3 ?6 f- x' X* g
nums 是一个非递减数组
; H7 a" C8 M& D2 k) W1 \
-10(9) <= target <= 10(9)
( t4 i, `. T3 V0 D
思路
, j: l: m1 D$ i1 A3 l
关键步骤，与二分查找不同
1 z, ?3 C% I. \/ v6 U8 V3 r3 i
if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
$ n# }& e. c" A
target==nums[mid]时，不结束循环，继续进入
3 `* N& l' _/ ]$ t% I; u
两个if可以同时进入，寻找界限
: V7 Q" S% }, ]8 O0 Z2 A! b
设置限制，防止mid-1,mid+1越界
% y; W% q- Q% _
代码
- H8 i& ^! o5 D s4 z8 m2 ~
class Solution {
, J, b# A, M% `. l
public:
3 _1 P6 E# _7 A5 k4 Q
int left=-1,right=-1;
2 C Q" J! a5 k) z
vector<int> searchRange(vector<int>& nums, int target) {
. |$ m2 M5 E* Q
if(nums.size()==0) return vector<int>{-1,-1};
( X8 k0 L' d5 v6 M& p& [2 s
binary_search(nums,target,0,nums.size());
9 L$ C, `, L- r$ b* Q6 ?( v
return vector<int>{left,right};
( @; u3 }6 m! f
}
; {6 m+ f* ?0 C h# L, k1 W" L( z$ F
void binary_search(vector<int>& nums,int target,int l ,int r){
8 ?2 d0 l9 v! c) p- {4 @
int mid=(r-l)/2+l;
( h. ^! Y [$ p5 }9 T3 _
//printf("%d-%d\n",l,r);
: X! k9 Q! E! @ u; v0 N
if(target==nums[mid]){
& ^; D, o! A4 f; {
if(left>mid||left<0) left=mid;
, _$ f2 B- f# I) T* i
if(right<mid||right<0) right=mid;
1 Q: E) _6 C8 B) X b/ L3 v
}
1 y! P% [& }- @+ _- H; g4 t
if(l>=r) return;
0 W: u# ` ~# c4 B! q8 D
if(target<=nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
+ d+ d! k4 B/ Y2 ]+ Z$ Y3 b
if(target>=nums[mid]&&mid+1<nums.size()) binary_search(nums,target,mid+1,r);
) ^- W# }0 i2 g& Y4 z' Q! R9 x
}
, v: g0 i( u0 s, r( h( g, t; h
};
. ^' ^) C4 q; A1 K8 `
1 d- o3 a" {9 s) B
————————————————
& O5 V2 O D5 ^2 c: Q, d3 g
版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" B J- ]6 s Z# R
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832
+ v$ _# U9 ~2 X9 k0 D$ Y
) x6 E0 z3 ^; @. y) [7 w
$ G" x- q U, ?) z8 H1 A! @
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5