内容简介:Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.Your algorithm's runtime complexity must be in the order of O(log n).If the target is not found in the array, return [-1, -1].
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
难度:medium
题目:
给定一升序整数数组,找出给定整数的起止边界。算法时间复杂度要为O(log n)
思路:二叉搜索
Runtime: 4 ms, faster than 65.40% of Java online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 30.5 MB, less than 28.29% of Java online submissions for Find First and Last Position of Element in Sorted Array.
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = binarySearch(nums, false, target);
result[1] = binarySearch(nums, true, target);
return result;
}
// false -> left, true -> right
private int binarySearch(int[] nums, boolean direction, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
if (direction && mid < nums.length - 1 && nums[mid + 1] == target) {
left = mid + 1;
} else if (!direction && mid > 0 && nums[mid - 1] == target) {
right = mid - 1;
} else {
return mid;
}
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Beginning Java Objects中文版从概念到代码
巴克 / 万波 / 人民邮电出版社 / 2007-1 / 78.00元
《Beginning Java Objects中文版从概念到代码(第2版)》是关于软件对象和Java的,但并不是纯粹地介绍Java语言,而是强调如何从对象模型转换到功能完整的Java应用程序。书中讲述了对象基础、对象建模和模型的实现。《Beginning Java Objects中文版从概念到代码(第2版)》除了用学生注册系统(SRS)示例贯穿全书之外,还在附录中给出三个附加的案例,这些案例是每章......一起来看看 《Beginning Java Objects中文版从概念到代码》 这本书的介绍吧!