当前位置:网站首页>【Hot100】34. Find the first and last positions of elements in a sorted array
【Hot100】34. Find the first and last positions of elements in a sorted array
2022-07-05 13:14:00 【Wang Liuliu's it daily】
34. Find the first and last positions of the elements in the sort array
Medium question
Give you an answer The decreasing An array of integers arranged in sequence nums, And a target value target.
Please find out the start position and end position of the given target value in the array .
If the target value does not exist in the array target, return [-1, -1].
You must design and implement a time complexity of O(log n) The algorithm to solve this problem .
Answer key :
Within a range , Find a number , Ask to find the start and end positions of this element , The numbers in this range are monotonically increasing , That is, it has monotonic property , So you can use dichotomy to do .
Two bisections , The first dichotomy finds the first t>=target The location of , The second dichotomy looks for the last t<=target The location of .
If the search is successful, two position subscripts will be returned , Otherwise return to [-1,-1].
- Template I : When we will interval [l, r] Divide into [l,mid] and [mid + 1, r] when , The update operation is r = mid perhaps l = mid + 1, Calculation mid There is no need to add 1, namely mid=(l+r)/2.
- Template II : When we will interval [l, r] Divide into [l,mid−1] and [mid,r] when , The update operation is r=mid−1 perhaps l=mid, In order to prevent the dead cycle , Calculation mid Need to add 1, namely mid=(l+r+1)/2.
Be careful :
When the left boundary is to be updated to l = mid
when , Order mid =(l + r + 1)/2
, Equivalent to rounding up , It won't be because r Take a special value r = l + 1
And fall into a dead circle .
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0) {
return new int[]{
-1,-1};
}
int l = 0, r = nums.length - 1; // Dichotomous range
while( l < r) // Find the starting position of the element
{
int mid = (l + r )/2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if( nums[r] != target) {
return new int[]{
-1,-1}; // To find the failure
}
int L = r;
l = 0;
r = nums.length - 1; // Dichotomous range
while( l < r) // Find the end position of the element
{
int mid = (l + r + 1)/2;
if(nums[mid] <= target ) l = mid;
else r = mid - 1;
}
return new int[]{
L,r};
}
}
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0){
return new int[]{
-1,-1};
}
int l = 0, r = nums.length - 1; // Dichotomous range Left and right closed
// Find the starting position of the element
while( l < r){
int mid = (l + r )/2;
if(nums[mid] >= target){
r = mid;
} else{
l = mid + 1;
}
}
if( nums[r] != target){
return new int[]{
-1,-1}; // To find the failure
}
int L = r;
l = 0; r = nums.length - 1; // Dichotomous range
// Find the end position of the element
while( l < r)
{
int mid = (l + r + 1)/2; // Be careful
if(nums[mid] <= target ){
l = mid;
} else {
r = mid - 1;
}
}
return new int[]{
L,r};
}
}
边栏推荐
- 山东大学暑期实训一20220620
- go map
- 【Hot100】34. 在排序数组中查找元素的第一个和最后一个位置
- 碎片化知识管理工具Memos
- FPGA 学习笔记:Vivado 2019.1 添加 IP MicroBlaze
- 同事半个月都没搞懂selenium,我半个小时就给他整明白!顺手秀了一波爬淘宝的操作[通俗易懂]
- 《2022年中國銀行業RPA供應商實力矩陣分析》研究報告正式啟動
- Yyds dry inventory JS intercept file suffix
- How can non-technical departments participate in Devops?
- leetcode:221. Maximum square [essence of DP state transition]
猜你喜欢
Go array and slice
Shu tianmeng map × Weiyan technology - Dream map database circle of friends + 1
SAE international strategic investment geometry partner
A specific example of ABAP type and EDM type mapping in SAP segw transaction code
CAN和CAN FD
FPGA 学习笔记:Vivado 2019.1 添加 IP MicroBlaze
RHCSA9
Talk about seven ways to realize asynchronous programming
CF:A. The Third Three Number Problem【关于我是位运算垃圾这个事情】
SAP UI5 DynamicPage 控件介紹
随机推荐
FPGA 学习笔记:Vivado 2019.1 添加 IP MicroBlaze
JXL notes
Introduction to the principle of DNS
go 字符串操作
精彩速递|腾讯云数据库6月刊
Flutter InkWell & Ink组件
Write macro with word
A small talk caused by the increase of sweeping
Go array and slice
Talking about fake demand from takeout order
Get you started with Apache pseudo static configuration
Introduction to sap ui5 dynamicpage control
Hundred days to complete the open source task of the domestic database opengauss -- openguass minimalist version 3.0.0 installation tutorial
实现 1~number 之间,所有数字的加和
946. 验证栈序列
Rocky基础知识1
Discussion on error messages and API versions of SAP ui5 getsaplogonlanguage is not a function
Principle and configuration of RSTP protocol
Pandora IOT development board learning (HAL Library) - Experiment 7 window watchdog experiment (learning notes)
Shandong University Summer Training - 20220620