【算法hot-34】在排序数组中查找元素的第一个和最后一个位置
2023-09-27 14:29:28 时间
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
public class LC011_34_searchRange {
public static void main(String[] args) {
int[] ints = {5, 7, 7, 8, 8, 10};
int[] ints1 = searchRange(ints, 8);
for (int i : ints1) {
System.out.println(i);
}
}
public static int[] searchRange(int[] nums, int target) {
int left = index(nums, target - 1);
int right = index(nums, target) - 1;
if (left <= right && nums[left] == target && nums[right] == target) {
return new int[]{left, right};
}
return new int[]{-1, -1};
}
private static int index(int[] nums, int target) {
int left = 0, right = nums.length - 1, ans = nums.length;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
}
相关文章
- TypeScript算法题实战——剑指 Offer篇(1)
- 【机器学习】聚类算法:层次聚类、K-means聚类
- 人工智能-损失函数-优化算法:梯度下降法的背后原理【一阶泰勒展开】
- 基于图搜索的规划算法之Dijkstra
- CCF CCSP2016:算法编程是最基本、最重要的能力
- js多个(N)个数组的的元素组合排序算法,多维数组的排列组合或多个数组之间的排列组合
- 自制无限级分类算法。
- hdu 1385 Minimum Transport Cost (floyd算法)
- 算法学习之数组和字符串
- LeetCode_贪心算法_中等_1775.通过最少操作次数使数组的和相等
- LeetCode_贪心算法_中等_945.使数组唯一的最小增量
- Python3入门机器学习经典算法与应用 第3章 Numpy数组的合并与分割
- 算法(1)- 删除有序数组中的重复项
- 【笔记】JavaScript版数据结构与算法——基础算法之“数组类”(89. 格雷编码)
- 针对范围对的高效查找算法设计(不准用数组)
- 算法4-6:关联数组的基本实现
- 算法:将一个数组旋转k步
- 算法:实现两个大数字相加
- 搜索中常见数据结构与算法探究(一)
- 数据结构和算法 (二)数据结构基础、线性表、栈和队列、数组和字符串
- 一道某度的笔试算法题
- Keras版faster-rcnn算法详解(RPN计算)
- 【音频处理】Melodyne 导入音频 ( 使用 Adobe Audition 录制音频 | 在 Melodyne 中打开录制的音频 | Melodyne 对音频素材的操作 | 音频分析算法 )