腾讯&字节&leetcode34：在排序数组中查找元素的第一个和最后一个位置 #84

Activity

1. sisterAn

   added

   LeetCode

   字节

   腾讯

   on Jul 16, 2020
2. Cxy56 commented on Jul 17, 2020

   

   Cxy56

   on Jul 17, 2020

   Last edited by sisterAn

   More actions

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

   👍React with 👍1Reacted by Ryan
3. sisterAn commented on Jul 19, 2020

   

   sisterAn

   on Jul 19, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解答一：findIndex、lastIndexOf

   findIndex() 方法返回数组中满足提供的测试函数的第一个元素的索引。若没有找到对应元素则返回-1。

   lastIndexOf() 方法返回指定元素（也即有效的 JavaScript 值或变量）在数组中的最后一个的索引，如果不存在则返回 -1。

   解答二：二分查找

   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)

   👍React with 👍2Reacted by jecyu and Bbottle
4. Airfald commented on Sep 23, 2020

   

   Airfald

   on Sep 23, 2020

   Last edited by Airfald

   More actions

   嗯，这算法可以， 但是在真正项目中我愿意用 findIndex , findLastIndex

   👍React with 👍3Reacted by empty, Jin Yao and Showbuger
5. XW666 commented on Apr 14, 2021

   

   XW666

   on Apr 14, 2021

   Last edited by XW666

   More actions

   ###  const comfiles = (arr, val) => {
       let sta = -1, end = -1;
       let obj = {}
       arr.forEach((item, index) => {
         if (item === val) {
           if (obj[item]) {
             end = index
           } else {
             obj[item] = index
             sta = index
           }
         }
       })
       return [sta, end]
     }
   
6. JYone223 commented on Apr 19, 2021

   

   JYone223

   on Apr 19, 2021

   More actions

   简化的二分查找

   var searchRange = function(nums, target) {
     let mid;
     let low = 0;
     let high = nums.length - 1;
   
     while (low <= high) {
       mid = Math.floor((low + high) / 2);
       if (nums[mid] === target) {
         let start = end = mid;
         while (nums[start] === target) start--;
         while (nums[end] === target) end++;
   
         return [start + 1, end - 1];
       }
   
       if (nums[mid] > target) {
         high = mid - 1;
       } else {
         low = mid + 1;
       }
     }
   
     return [-1, -1];
   }
   

   👍React with 👍3Reacted by AAAngelina, Ryan and arieslx
7. KylinLee commented on Apr 19, 2021

   

   KylinLee

   on Apr 19, 2021

   More actions

   二分查找找到后，双指针同时向前向后查找。

   👍React with 👍1Reacted by AAAngelina