我正在尝试解决LeetCode问题Find First and Last Position of Element in Sorted Array:
给定一个按升序排序的整数数组nums
,找到给定target
值的起始和结束位置。
如果在数组中找不到target
,则返回[-1, -1]
。
您必须编写运行时复杂度为O(log n)
的算法。
我正在写这段代码:
var searchRange = function(nums, target) {
nums = nums.sort((a, b) => (a-b))
let result = [];
for(let i = 0; i < nums.length; i++) {
if (nums[i] == target) {
result.push(i)
} else {
result = [-1, -1]
}
}
return result
};
console.log(searchRange([5,7,7,8,8,10], 8));
它应返回:
[3, 4]
但它返回:
[-1, -1]
有什么不对吗?
5条答案
按热度按时间g6baxovj1#
您的
else
代码正在清除循环的上一次迭代的结果。但是,您的代码效率不高:
首先,它在一个给定的已经排序的数组上调用
sort
:那就别说了。时间复杂度为O(n),而不是O(logn),所以,如果你的时间复杂度为O(n),那么你的时间复杂度为O(n)。
如果要得到O(logn),您需要实现一个二进制搜索,然后执行一个搜索来找到范围的 start,再执行另一个搜索来找到它的结尾。
以下是具体的操作方法:
q5lcpyga2#
您的循环没有良好的退出条件。循环迭代直到最后一个元素,如果最后一个元素不匹配,则将-1、-1设置到结果中。result的中间值将被忽略。
其他问题:
解决方法:
rta7y2nd3#
bbmckpt74#
你的思路是正确的,这只是你的逻辑。如果最后一个
target
索引之后的nums
的任何索引不等于target
,你就将result
设置为[-1,-1]。所以你想在for
循环之外进行检查。注意:这不是最终解决方案,因为这将返回包含
target
的每个索引368yc8dk5#
"飞镖"