【LeetCode-面试算法经典-Java实现】【034-Search for a Range(搜索一个范围)】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode-面试算法经典-Java实现】【034-Search for a Range(搜索一个范围)】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2494字,纯文字阅读大概需要4分钟。
内容图文
![【LeetCode-面试算法经典-Java实现】【034-Search for a Range(搜索一个范围)】](/upload/InfoBanner/zyjiaocheng/1324/c006c13547c0404f9d5f063510d9f3f2.jpg)
【034-Search for a Range(搜索一个范围)】
【LeetCode-面试算法经典-Java实现】【所有题目目录索引】
原题
Given a sorted array of integers, 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]
.
For example,
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4]
.
题目大意
给定一个排好序的数组,同时给定一个要查找的值 ,找出这个数在数组中的出现在起始和结束位置。
算法的时间复杂度要求为log(N)。
如果没有找到就返回[-1, -1]
解题思路
(假定数组是递增有序的)先用二分查找算法看数组中是否存在这个数,如果不存在就返回[-1,-1]
如果存在就分别找这个数最后一次出来现的位置和最开始出现的位置。找最后出现的位置时,先从数组最后一个位置开始找,如果大于待找的值,就前近一个位置,还大于就前近2个,以2找指数数增加,如果小于就退回到原来位置的后一个进行查找,重新按1,2,4、、、这样子的方式进行,直到找到为止。对于找最先的元素也是一样的。
代码实现
算法实现类
public
class
Solution {
public
int[] searchRange(int[] A, int target) {
if (A == null || A.length == 0) {
returnnewint[]{-1, -1};
}
int lo = 0;
int hi = A.length - 1;
int mi = 0;
// 查找数组中是否存在值为target的元素while (lo <= hi) {
mi = lo + (hi - lo) / 2;
if (target < A[mi]) {
hi = mi - 1;
} elseif (target > A[mi]) {
lo = mi + 1;
} else {
break;
}
}
if (A[mi] != target) {
returnnewint[]{-1, -1};
}
lo = searchFirst(A, 0, mi, target);
hi = searchLast(A, mi, A.length - 1, target);
returnnewint[]{lo, hi};
}
/**
* 找target最先出现的位置,查找的范围是[lo, hi],A[hi]等于target,A为有序数组
*
* @param A 待查找的数组
* @param lo 查找的起始位置
* @param hi 查找的结束位置
* @param target 查找的值
* @return target最先出现的位置
*/privateintsearchFirst(int[] A, int lo, int hi, int target) {
int gap = 1;
do {
hi -= gap;
if (hi < lo || A[hi] != target) {
hi += gap;
if (hi <= lo || A[hi - 1] != target) {
return hi;
} else {
gap = 1;
hi--;
}
} else {// 在上一次的位置后退gap个依然相等
gap *= 2;
}
} while (true);
}
/**
* 找target最后出现的位置,查找的范围是[lo, hi],A[lo]等于target,A为有序数组
*
* @param A 待查找的数组
* @param lo 查找的起始位置
* @param hi 查找的结束位置
* @param target 查找的值
* @return target最后出现的位置
*/privateintsearchLast(int[] A, int lo, int hi, int target) {
int gap = 1;
do {
lo += gap;
if (lo > hi || A[lo] != target) {
lo -= gap;
if (lo >= hi || A[lo + 1] != target) {
return lo;
} else {
gap = 1;
lo++;
}
} else {// 在上一次的位置前进gap个依然相等
gap *= 2;
}
} while (true);
}
}
评测结果
点击图片,鼠标不释放,拖动一段位置,释放后在新的窗口中查看完整图片。
特别说明
欢迎转载,转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47079319】
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/derrantcm/article/details/47079319
内容总结
以上是互联网集市为您收集整理的【LeetCode-面试算法经典-Java实现】【034-Search for a Range(搜索一个范围)】全部内容,希望文章能够帮你解决【LeetCode-面试算法经典-Java实现】【034-Search for a Range(搜索一个范围)】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。