javascript 查找排序数组中元素的第一个和最后一个位置

xurqigkl  于 2022-12-02  发布在  Java
关注(0)|答案(5)|浏览(276)

我正在尝试解决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]

有什么不对吗?

g6baxovj

g6baxovj1#

您的else代码正在清除循环的上一次迭代的结果。
但是,您的代码效率不高:
首先,它在一个给定的已经排序的数组上调用sort:那就别说了。
时间复杂度为O(n),而不是O(logn),所以,如果你的时间复杂度为O(n),那么你的时间复杂度为O(n)。
如果要得到O(logn),您需要实现一个二进制搜索,然后执行一个搜索来找到范围的 start,再执行另一个搜索来找到它的结尾。
以下是具体的操作方法:

function binarySearch(nums, target) {
    let low = 0;
    let high = nums.length;
    
    while (low < high) {
        let mid = (low + high) >> 1; // half way
        if (nums[mid] > target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return high; // first index AFTER target
}

function searchRange(nums, target) {
    let end = binarySearch(nums, target);
    let start = binarySearch(nums, target - 1);
    return start === end ? [-1, -1] : [start, end - 1];
}
 
console.log(searchRange([5,7,7,8,8,10], 8));
q5lcpyga

q5lcpyga2#

您的循环没有良好的退出条件。循环迭代直到最后一个元素,如果最后一个元素不匹配,则将-1、-1设置到结果中。result的中间值将被忽略。
其他问题:

  • 你得到了一个排序数组,所以不要再排序了。这很麻烦。
  • 时间复杂度为O(n),时间复杂度为O(n)。

解决方法:

  • 二进制搜索查找元素的任何一个示例-保存找到该值的索引。
  • 使用index found检查原始数组中左右相邻的元素,以找出起始和结束位置。
rta7y2nd

rta7y2nd3#

function searchRange(r,n){
  var s = r.sort((a,b)=>a-b);
  return [s.indexOf(n), s.lastIndexOf(n)];
}

console.log('result 1',searchRange([5,7,7,8,8,10], 8))
console.log('result 2',searchRange([5,7,7,6,6,10], 8))
bbmckpt7

bbmckpt74#

你的思路是正确的,这只是你的逻辑。如果最后一个target索引之后的nums的任何索引不等于target,你就将result设置为[-1,-1]。所以你想在for循环之外进行检查。

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);
        }
    }

    return (result.length == 0) ? [-1, -1] : result;
};
 
 console.log(searchRange([5,7,7,8,8,10], 8));

注意:这不是最终解决方案,因为这将返回包含target的每个索引

368yc8dk

368yc8dk5#

"飞镖"

if (nums.isEmpty || !nums.contains(target)) {
      return [-1, -1];
    } else {
      return [nums.indexOf(target), nums.lastIndexOf(target)];
    }

相关问题