Open xszi opened 3 years ago
方法一:使用 findIndex , findLastIndex
方法二:
var searchRange = function(nums, target) {
let left = 0, right = nums.length -1
let start = -1, end = -1
while(left <= right) {
if(nums[left] < target) left++
// 找到第一个出现的位置,赋值给start
if(nums[left] === target && start === -1) start = left++
if(nums[right] > target) right--
// 找到最后一个出现的位置,赋值给end
if(nums[right] === target && end === -1) end = right--
if(start > -1 && end > -1) break
}
return [start, end]
};
方法三:二分查找
let searchRange = function(nums, target) {
return [leftSearch(nums, target), rightSearch(nums, target)]
}
let leftSearch = function(nums, target) { let low = 0, high = nums.length - 1, mid while (low <= high) { mid = Math.floor((low+high)/2) if (nums[mid] < target) { low = mid + 1 } else if (nums[mid] > target) { high = mid - 1 } else if (nums[mid] === target) { // 这里不返回,继续收缩左侧边界 high = mid - 1 } } // 最后检查 low 是否越界或命中 if (low >= nums.length || nums[low] != target) return -1 return low }
let rightSearch = function (nums, target) { let low = 0, high = nums.length - 1, mid while (low <= high) { mid = Math.floor((low+high)/2) if (nums[mid] < target) { low = mid + 1 } else if (nums[mid] > target) { high = mid - 1 } else if (nums[mid] === target) { // 这里不返回,继续收缩右侧边界 low = mid + 1 } } // 最后检查 high 是否越界或命中 if (high < 0 || nums[high] != target) return -1 return high }
复杂度分析:
* 时间复杂度:O(logn)
* 空间复杂度:O(1)
给定一个按照升序排列的整数数组
nums
,和一个目标值target
。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是
O(logn)
级别。如果数组中不存在目标值,返回
[-1, -1]
。示例 1:
示例 2:
leetcode