We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
给定一个按照升序排列的整数数组 nums,和一个目标值 target 。找出给定目标值在数组中的开始位置和结束位置。
nums
target
你的算法时间复杂度必须是O(logn)级别。
O(logn)
如果数组中不存在目标值,返回 [-1, -1] 。
[-1, -1]
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
leetcode
The text was updated successfully, but these errors were encountered:
方法一:使用 findIndex , findLastIndex
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 }
复杂度分析:
Sorry, something went wrong.
No branches or pull requests
给定一个按照升序排列的整数数组
nums
,和一个目标值target
。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是
O(logn)
级别。如果数组中不存在目标值,返回
[-1, -1]
。示例 1:
示例 2:
leetcode
The text was updated successfully, but these errors were encountered: