Leetcode刷题(第34题)——在排序数组中查找元素的第一个和最后一个位置

x33g5p2x  于2022-02-28 转载在 其他  
字(0.6k)|赞(0)|评价(0)|浏览(358)

一、题目

二、示例

  1. 示例一
  2. 输入:nums = [5,7,7,8,8,10], target = 8
  3. 输出:[3,4]
  4. 示例二:
  5. 输入:nums = [5,7,7,8,8,10], target = 6
  6. 输出:[-1,-1]
  7. 示例三:
  8. 输入:nums = [], target = 0
  9. 输出:[-1,-1]

三、思路
时间复杂度为O(logn),肯定是二分查找,只不过需要在找到值后,然后再在该下标周围查找是否存在和target相等的值。
四、代码解题

  1. /**
  2. * @param {number[]} nums
  3. * @param {number} target
  4. * @return {number[]}
  5. */
  6. var searchRange = function(nums, target) {
  7. let left = 0
  8. let length = nums.length
  9. let right = length - 1
  10. let ret = -1
  11. while(left <= right) {
  12. let mid = Math.floor((left + right) / 2)
  13. if(target === nums[mid]) {
  14. ret = mid
  15. let l = ret - 1
  16. let r = ret + 1
  17. while(l >= 0 && nums[l] === target) {
  18. l--
  19. }
  20. while(r < length && nums[r] === target) {
  21. r++
  22. }
  23. return [l+1, r-1]
  24. }else if(target > nums[mid]) {
  25. left = mid + 1
  26. }else {
  27. right = mid - 1
  28. }
  29. }
  30. return [-1, -1]
  31. };

五、结果

相关文章