当前位置:网站首页>【LeetCode-34】在排序数组中查找元素的第一个和最后一个位置
【LeetCode-34】在排序数组中查找元素的第一个和最后一个位置
2022-08-11 05:30:00 【Ring*】
10.4 在排序数组中查找元素的第一个和最后一个位置【34】
10.4.1 题目描述
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
10.4.2 方法一:二分查找
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
return new int[]{
leftIdx, rightIdx};
}
return new int[]{
-1, -1};
}
public int binarySearch(int[] nums, int target, boolean lower) {
int left = 0, right = nums.length - 1, ans = nums.length;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
}
复杂度分析
- 时间复杂度: O(logn) ,其中 nn 为数组的长度。二分查找的时间复杂度为 O(logn),一共会执行两次,因此总时间复杂度为 O(logn)。
- 空间复杂度:O(1) 。只需要常数空间存放若干变量。
10.4.3 my answer—二分查找
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length -1 ;
int ans = -1;
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid]>target){
right = mid - 1;
}else if(nums[mid]<target){
left = mid + 1;
}else{
ans = mid;
break;
}
}
if(ans==-1)return new int[]{
-1,-1};
int ans_left = ans;
int ans_right = ans;
while(true){
ans_left--;
if(ans_left<0 || nums[ans_left] != target){
break;
}
}
while(true){
ans_right++;
if(ans_right>nums.length-1 || nums[ans_right] != target){
break;
}
}
return new int[]{
ans_left+1,ans_right-1};
}
}
边栏推荐
猜你喜欢
星盟-pwn-babyheap
Use the adb command to manage applications
Day 80
Jetpack's dataBinding
The official website of OpenMLDB is upgraded, and the mysterious contributor map will take you to advance quickly
buuctf hacknote
Real-time Feature Computing Platform Architecture Methodology and Practice Based on OpenMLDB
Jetpack之dataBinding
Visual studio2019 configuration uses pthread
swagger错误:WARN i.s.m.p.AbstractSerializableParameter - [getExample,421] - Illegal DefaultValue null
随机推荐
[Meetup Preview] OpenMLDB+OneFlow: Link feature engineering to model training to accelerate machine learning model development
手把手导入企业项目(快速完成本地项目配置)
编译异常解决
Day 78
精彩联动 | OpenMLDB Pulsar Connector原理和实操
swagger错误:WARN i.s.m.p.AbstractSerializableParameter - [getExample,421] - Illegal DefaultValue null
杀死进程-查看防火墙状态
C语言-7月22日- NULL和nullptr的深入了解以及VScode对nullptr语句报错问题的解决
Node 踩坑之80端口被占用
mk file introduction
127.0.0.1 已拒绝连接
jdbc接口文档参考,jdbc接口方法逻辑探究
Building a data ecology for feature engineering - Embrace the open source ecology, OpenMLDB fully opens up the MLOps ecological tool chain
SearchGuard configuration
无效的修订:3.18.1-g262b901-dirty
JS进阶网页特效(pink老师笔记)
Day 75
JNI入门
使用adb命令管理应用
PyQt5中调用.ui转换的.py文件代码解释