自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

在排序數(shù)組中查找元素的第一個和最后一個位置

作者：程序員Carl
開發(fā) 前端
給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

[[440116]]

這個就是考察二分法的進(jìn)階題目了

在排序數(shù)組中查找元素的第一個和最后一個位置

給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

進(jìn)階：你可以設(shè)計并實現(xiàn)時間復(fù)雜度為 O(log n) 的算法解決此問題嗎?

示例 1：

  • 輸入：nums = [5,7,7,8,8,10], target = 8
  • 輸出：[3,4]

示例 2：

  • 輸入：nums = [5,7,7,8,8,10], target = 6
  • 輸出：[-1,-1]

示例 3：

  • 輸入：nums = [], target = 0
  • 輸出：[-1,-1]

思路

這道題目如果基礎(chǔ)不是很好，不建議大家看簡短的代碼，簡短的代碼隱藏了太多邏輯，結(jié)果就是稀里糊涂把題AC了，但是沒有想清楚具體細(xì)節(jié)!

對二分還不了解的同學(xué)先做這兩題：

  • 704.二分查找
  • 35.搜索插入位置

下面我來把所有情況都討論一下。

尋找target在數(shù)組里的左右邊界，有如下三種情況：

  • 情況一：target 在數(shù)組范圍的右邊或者左邊，例如數(shù)組{3, 4, 5}，target為2或者數(shù)組{3, 4, 5},target為6，此時應(yīng)該返回{-1, -1}
  • 情況二：target 在數(shù)組范圍中，且數(shù)組中不存在target，例如數(shù)組{3,6,7},target為5，此時應(yīng)該返回{-1, -1}
  • 情況三：target 在數(shù)組范圍中，且數(shù)組中存在target，例如數(shù)組{3,6,7},target為6，此時應(yīng)該返回{1, 1}

這三種情況都考慮到，說明就想的很清楚了。

接下來，在去尋找左邊界，和右邊界了。

采用二分法來去尋找左右邊界，為了讓代碼清晰，我分別寫兩個二分來尋找左邊界和右邊界。

剛剛接觸二分搜索的同學(xué)不建議上來就像如果用一個二分來查找左右邊界，很容易把自己繞進(jìn)去，建議扎扎實實的寫兩個二分分別找左邊界和右邊界

尋找右邊界

先來尋找右邊界，至于二分查找，如果看過704.二分查找就會知道，二分查找中什么時候用while (left <= right)，有什么時候用while (left < right)，其實只要清楚循環(huán)不變量，很容易區(qū)分兩種寫法。

那么這里我采用while (left <= right)的寫法，區(qū)間定義為[left, right]，即左閉又閉的區(qū)間(如果這里有點看不懂了，強(qiáng)烈建議把704.二分查找這篇文章先看了，704題目做了之后再做這道題目就好很多了)

確定好：計算出來的右邊界是不包好target的右邊界，左邊界同理。

可以寫出如下代碼

  1. // 二分查找，尋找target的右邊界（不包括target） 
  2. // 如果rightBorder為沒有被賦值（即target在數(shù)組范圍的左邊，例如數(shù)組[3,3]，target為2），為了處理情況一 
  3. int getRightBorder(vector<int>& nums, int target) { 
  4.     int left = 0; 
  5.     int right = nums.size() - 1; // 定義target在左閉右閉的區(qū)間里，[left, right] 
  6.     int rightBorder = -2; // 記錄一下rightBorder沒有被賦值的情況 
  7.     while (left <= right) { // 當(dāng)left==right，區(qū)間[left, right]依然有效 
  8.         int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2 
  9.         if (nums[middle] > target) { 
  10.             right = middle - 1; // target 在左區(qū)間，所以[left, middle - 1] 
  11.         } else { // 當(dāng)nums[middle] == target的時候，更新left，這樣才能得到target的右邊界 
  12.             left = middle + 1; 
  13.             rightBorder = left; 
  14.         } 
  15.     } 
  16.     return rightBorder; 
  17. } 

尋找左邊界

  1. // 二分查找，尋找target的左邊界leftBorder（不包括target） 
  2. // 如果leftBorder沒有被賦值（即target在數(shù)組范圍的右邊，例如數(shù)組[3,3],target為4），為了處理情況一 
  3. int getLeftBorder(vector<int>& nums, int target) { 
  4.     int left = 0; 
  5.     int right = nums.size() - 1; // 定義target在左閉右閉的區(qū)間里，[left, right] 
  6.     int leftBorder = -2; // 記錄一下leftBorder沒有被賦值的情況 
  7.     while (left <= right) { 
  8.         int middle = left + ((right - left) / 2); 
  9.         if (nums[middle] >= target) { // 尋找左邊界，就要在nums[middle] == target的時候更新right 
  10.             right = middle - 1; 
  11.             leftBorder = right; 
  12.         } else { 
  13.             left = middle + 1; 
  14.         } 
  15.     } 
  16.     return leftBorder; 
  17. } 

處理三種情況

左右邊界計算完之后，看一下主體代碼，這里把上面討論的三種情況，都覆蓋了

  1. class Solution { 
  2. public: 
  3.     vector<int> searchRange(vector<int>& nums, int target) { 
  4.         int leftBorder = getLeftBorder(nums, target); 
  5.         int rightBorder = getRightBorder(nums, target); 
  6.         // 情況一 
  7.         if (leftBorder == -2 || rightBorder == -2) return {-1, -1}; 
  8.         // 情況三 
  9.         if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1}; 
  10.         // 情況二 
  11.         return {-1, -1}; 
  12.     } 
  13. private: 
  14.      int getRightBorder(vector<int>& nums, int target) { 
  15.         int left = 0; 
  16.         int right = nums.size() - 1; 
  17.         int rightBorder = -2; // 記錄一下rightBorder沒有被賦值的情況 
  18.         while (left <= right) { 
  19.             int middle = left + ((right - left) / 2); 
  20.             if (nums[middle] > target) { 
  21.                 right = middle - 1; 
  22.             } else { // 尋找右邊界，nums[middle] == target的時候更新left 
  23.                 left = middle + 1; 
  24.                 rightBorder = left; 
  25.             } 
  26.         } 
  27.         return rightBorder; 
  28.     } 
  29.     int getLeftBorder(vector<int>& nums, int target) { 
  30.         int left = 0; 
  31.         int right = nums.size() - 1; 
  32.         int leftBorder = -2; // 記錄一下leftBorder沒有被賦值的情況 
  33.         while (left <= right) { 
  34.             int middle = left + ((right - left) / 2); 
  35.             if (nums[middle] >= target) { // 尋找左邊界，nums[middle] == target的時候更新right 
  36.                 right = middle - 1; 
  37.                 leftBorder = right; 
  38.             } else { 
  39.                 left = middle + 1; 
  40.             } 
  41.         } 
  42.         return leftBorder; 
  43.     } 
  44. }; 

這份代碼在簡潔性很有大的優(yōu)化空間，例如把尋找左右區(qū)間函數(shù)合并一起。

但拆開更清晰一些，而且把三種情況以及對應(yīng)的處理邏輯完整的展現(xiàn)出來了。

總結(jié)

初學(xué)者建議大家一塊一塊的去分拆這道題目，正如本題解描述，想清楚三種情況之后，先專注于尋找右區(qū)間，然后專注于尋找左區(qū)間，左右根據(jù)左右區(qū)間做最后判斷。

不要上來就想如果一起尋找左右區(qū)間，搞著搞著就會顧此失彼，繞進(jìn)去拔不出來了。

其他語言版本

Java

  1. class Solution { 
  2.     int[] searchRange(int[] nums, int target) { 
  3.         int leftBorder = getLeftBorder(nums, target); 
  4.         int rightBorder = getRightBorder(nums, target); 
  5.         // 情況一 
  6.         if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1}; 
  7.         // 情況三 
  8.         if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1}; 
  9.         // 情況二 
  10.         return new int[]{-1, -1}; 
  11.     } 
  12.  
  13.     int getRightBorder(int[] nums, int target) { 
  14.         int left = 0; 
  15.         int right = nums.length - 1; 
  16.         int rightBorder = -2; // 記錄一下rightBorder沒有被賦值的情況 
  17.         while (left <= right) { 
  18.             int middle = left + ((right - left) / 2); 
  19.             if (nums[middle] > target) { 
  20.                 right = middle - 1; 
  21.             } else { // 尋找右邊界，nums[middle] == target的時候更新left 
  22.                 left = middle + 1; 
  23.                 rightBorder = left; 
  24.             } 
  25.         } 
  26.         return rightBorder; 
  27.     } 
  28.  
  29.     int getLeftBorder(int[] nums, int target) { 
  30.         int left = 0; 
  31.         int right = nums.length - 1; 
  32.         int leftBorder = -2; // 記錄一下leftBorder沒有被賦值的情況 
  33.         while (left <= right) { 
  34.             int middle = left + ((right - left) / 2); 
  35.             if (nums[middle] >= target) { // 尋找左邊界，nums[middle] == target的時候更新right 
  36.                 right = middle - 1; 
  37.                 leftBorder = right; 
  38.             } else { 
  39.                 left = middle + 1; 
  40.             } 
  41.         } 
  42.         return leftBorder; 
  43.     } 
  44. } 
  1. // 解法2 
  2. // 1、首先，在 nums 數(shù)組中二分查找 target； 
  3. // 2、如果二分查找失敗，則 binarySearch 返回 -1，表明 nums 中沒有 target。此時，searchRange 直接返回 {-1, -1}； 
  4. // 3、如果二分查找成功，則 binarySearch 返回 nums 中值為 target 的一個下標(biāo)。然后，通過左右滑動指針，來找到符合題意的區(qū)間 
  5.  
  6. class Solution { 
  7.  public int[] searchRange(int[] nums, int target) { 
  8.   int index = binarySearch(nums, target); // 二分查找 
  9.  
  10.   if (index == -1) { // nums 中不存在 target，直接返回 {-1, -1} 
  11.    return new int[] {-1, -1}; // 匿名數(shù)組 
  12.   } 
  13.   // nums 中存在 targe，則左右滑動指針，來找到符合題意的區(qū)間 
  14.   int left = index; 
  15.   int right = index; 
  16.         // 向左滑動，找左邊界 
  17.   while (left - 1 >= 0 && nums[left - 1] == nums[index]) { // 防止數(shù)組越界。邏輯短路，兩個條件順序不能換 
  18.    left--; 
  19.   } 
  20.         // 向左滑動，找右邊界 
  21.   while (right + 1 < nums.length && nums[right + 1] == nums[index]) { // 防止數(shù)組越界。 
  22.    right++; 
  23.   } 
  24.   return new int[] {left, right}; 
  25.     } 
  26.  
  27.  /** 
  28.   * 二分查找 
  29.   * @param nums 
  30.   * @param target 
  31.   */ 
  32.  public int binarySearch(int[] nums, int target) { 
  33.   int left = 0; 
  34.   int right = nums.length - 1; // 不變量：左閉右閉區(qū)間 
  35.  
  36.   while (left <= right) { // 不變量：左閉右閉區(qū)間 
  37.    int mid = left + (right - left) / 2; 
  38.    if (nums[mid] == target) { 
  39.     return mid; 
  40.    } else if (nums[mid] < target) { 
  41.     left = mid + 1; 
  42.    } else { 
  43.     right = mid - 1; // 不變量：左閉右閉區(qū)間 
  44.    } 
  45.   } 
  46.   return -1; // 不存在 
  47.  } 
  48. } 

Python

  1. class Solution: 
  2.     def searchRange(self, nums: List[int], target: int) -> List[int]: 
  3.         def getRightBorder(nums:List[int], target:int) -> int: 
  4.             left, right = 0, len(nums)-1 
  5.             rightBoder = -2 # 記錄一下rightBorder沒有被賦值的情況 
  6.             while left <= right: 
  7.                 middle = left + (right-left) // 2 
  8.                 if nums[middle] > target: 
  9.                     right = middle - 1 
  10.                 else: # 尋找右邊界，nums[middle] == target的時候更新left 
  11.                     left = middle + 1 
  12.                     rightBoder = left 
  13.  
  14.             return rightBoder 
  15.  
  16.         def getLeftBorder(nums:List[int], target:int) -> int: 
  17.             left, right = 0, len(nums)-1 
  18.             leftBoder = -2 # 記錄一下leftBorder沒有被賦值的情況 
  19.             while left <= right: 
  20.                 middle = left + (right-left) // 2 
  21.                 if nums[middle] >= target: #  尋找左邊界，nums[middle] == target的時候更新right 
  22.                     right = middle - 1; 
  23.                     leftBoder = right; 
  24.                 else: 
  25.                     left = middle + 1 
  26.             return leftBoder 
  27.         leftBoder = getLeftBorder(nums, target) 
  28.         rightBoder = getRightBorder(nums, target) 
  29.         # 情況一 
  30.         if leftBoder == -2 or rightBoder == -2: return [-1, -1] 
  31.         # 情況三 
  32.         if rightBoder -leftBoder >1: return [leftBoder + 1, rightBoder - 1] 
  33.         # 情況二 
  34.         return [-1, -1] 
  1. # 解法2 
  2. # 1、首先，在 nums 數(shù)組中二分查找 target； 
  3. # 2、如果二分查找失敗，則 binarySearch 返回 -1，表明 nums 中沒有 target。此時，searchRange 直接返回 {-1, -1}； 
  4. # 3、如果二分查找成功，則 binarySearch 返回 nums 中值為 target 的一個下標(biāo)。然后，通過左右滑動指針，來找到符合題意的區(qū)間 
  5. class Solution: 
  6.     def searchRange(self, nums: List[int], target: int) -> List[int]: 
  7.         def binarySearch(nums:List[int], target:int) -> int: 
  8.             left, right = 0, len(nums)-1 
  9.             while left<=right: # 不變量：左閉右閉區(qū)間 
  10.                 middle = left + (right-left) // 2 
  11.                 if nums[middle] > target: 
  12.                     right = middle - 1 
  13.                 elif nums[middle] < target: 
  14.                     left = middle + 1 
  15.                 else: 
  16.                     return middle 
  17.             return -1 
  18.         index = binarySearch(nums, target) 
  19.         if index == -1:return [-1, -1] # nums 中不存在 target，直接返回 {-1, -1} 
  20.         # nums 中存在 targe，則左右滑動指針，來找到符合題意的區(qū)間 
  21.         left, right = index, index 
  22.         # 向左滑動，找左邊界 
  23.         while left -1 >=0 and nums[left - 1] == target: left -=1 
  24.         # 向右滑動，找右邊界 
  25.         while right+1 < len(nums) and nums[right + 1] == target: right +=1 
  26.         return [left, right] 
  1. # 解法3 
  2. # 1、首先，在 nums 數(shù)組中二分查找得到第一個大于等于 target的下標(biāo)（左邊界）與第一個大于target的下標(biāo)（右邊界）； 
  3. # 2、如果左邊界<= 右邊界，則返回 [左邊界, 右邊界]。否則返回[-1, -1] 
  4. class Solution: 
  5.     def searchRange(self, nums: List[int], target: int) -> List[int]: 
  6.         def binarySearch(nums:List[int], target:int, lower:bool) -> int: 
  7.             left, right = 0, len(nums)-1 
  8.             ans = len(nums) 
  9.             while left<=right: # 不變量：左閉右閉區(qū)間 
  10.                 middle = left + (right-left) //2 
  11.                 # lower為True，執(zhí)行前半部分，找到第一個大于等于 target的下標(biāo) ，否則找到第一個大于target的下標(biāo) 
  12.                 if nums[middle] > target or (lower and nums[middle] >= target): 
  13.                     right = middle - 1 
  14.                     ans = middle 
  15.                 else: 
  16.                     left = middle + 1 
  17.             return ans 
  18.  
  19.         leftBorder = binarySearch(nums, target, True) # 搜索左邊界 
  20.         rightBorder = binarySearch(nums, target, False) -1  # 搜索右邊界 
  21.         if leftBorder<= rightBorder and rightBorder< len(nums) and nums[leftBorder] == target and  nums[rightBorder] == target: 
  22.             return [leftBorder, rightBorder] 
  23.         return [-1, -1] 
  1. # 解法4 
  2. # 1、首先，在 nums 數(shù)組中二分查找得到第一個大于等于 target的下標(biāo)leftBorder； 
  3. # 2、在 nums 數(shù)組中二分查找得到第一個大于等于 target+1的下標(biāo)， 減1則得到rightBorder； 
  4. # 3、如果開始位置在數(shù)組的右邊或者不存在target，則返回[-1, -1] 。否則返回[leftBorder, rightBorder] 
  5. class Solution: 
  6.     def searchRange(self, nums: List[int], target: int) -> List[int]: 
  7.         def binarySearch(nums:List[int], target:int) -> int: 
  8.             left, right = 0, len(nums)-1 
  9.             while left<=right: # 不變量：左閉右閉區(qū)間 
  10.                 middle = left + (right-left) //2 
  11.                 if nums[middle] >= target: 
  12.                     right = middle - 1 
  13.                 else: 
  14.                     left = middle + 1 
  15.             return left  # 若存在target，則返回第一個等于target的值 
  16.  
  17.         leftBorder = binarySearch(nums, target) # 搜索左邊界 
  18.         rightBorder = binarySearch(nums, target+1) -1  # 搜索右邊界 
  19.         if leftBorder == len(nums) or nums[leftBorder]!= target: # 情況一和情況二 
  20.             return [-1, -1] 
  21.         return [leftBorder, rightBorder] 

 

責(zé)任編輯：姜華 來源： 代碼隨想錄
排序數(shù)組數(shù)據(jù)結(jié)構(gòu)算法
點贊
收藏

51CTO技術(shù)棧公眾號