ARTS-1-A Leetcode 34 题 [ 在已排序的列表中,查找目标数字的起止坐标 ]
题目链接:
Find First and Last Position of Element in Sorted Array
题目的大意就是给定一个升序的整形数组 nums 和一个目标数字 target ,要求返回一个数组,数组第一项是 target 在 nums 中第一次出现的下标,第二项是 target 在 nums 最后一次出现的下标。并且要求时间复杂度为 O(log n)。
思路
读完题目就可以判断出这道算法题考的查询算法,要求时间复杂度为 O(log n),直接遍历肯定是不行了,因此考察的二分查找算法,刚好时间复杂度是 O(log n)。
我的思路是先通过二分查找算法,做 nums 中找到任意一个 target 出现的下标,由于数组是升序的,找到一个下标后,分别向左右找到第一个和 target 不等的位置,就可以找出整个范围。
解题
实现如下:
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
const len = nums.length;
const i = binSearch(nums, 0, len - 1, target);
if (i == -1) {
return [-1, -1]
}
// 找到目标后,前后匹配,找出整个范围
const ret = [i, i];
let x = i;
while (x >= 0 && nums[x] == target) {
ret[0] = x;
x--;
}
x = i;
while (x < len && nums[x] == target) {
ret[1] = x;
x++;
}
return ret;
};
var binSearch = function(nums, start, end, target) {
var mid = Math.floor((start + end) / 2);
while (end >= start) {
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
mid = Math.floor((start + end) / 2);
}
return -1;
}
其中的二分查找方法,我们可以封装成一个方法,每次题目需要用到的时候,直接复制过来就可以了,很多常见的算法实现,熟练使用之后都可以这么做。
结果
下面看下结果:
时间上超过 84% 的提交,还算不错,内存使用算是中等。 一次提交通过后就可以查看其他人的提交,可以对比学习下,盲猜有人用了 js 自带的 indexOf 方法,这个方法的实现效率是比二分查找要快的。
对比
对比了下别人的提交记录,基本都使用了二分查找法,有一种不同的解法,是对二分查找稍作改造,保证每次查到的都是 target 第一次出现的位置,然后分别找到 target、target + 1 第一次出现的位置,因为是升序的数组,target + 1 第一次出现的下标 - 1 就是 target 最后出现的下标,运行速度比我上面贴的代码要快。
我考虑了下,认为应该是当 target 重复次数很多的情况下,通过寻找 target + 1 来确定 target 最后的下标,效率要更快。感兴趣的同学可以深入研究下。
ARTS
题目中的 ARTS 是耗子叔在他的极客专栏 左耳听风 中发起的个活动:
每周完成一个 ARTS: 至少做一个 LeetCode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。(也就是 Algorithm、Review、Tip、Share 简称 ARTS)