LeetCode——二分專題

LeetCode——二分

69. x 的平方根

實作 int sqrt(int x) 函式，

計算并回傳 x 的平方根，其中 x 是非負整數，

由于回傳型別是整數，結果只保留整數的部分，小數部分將被舍去，

示例 :

輸入: 4
輸出: 2

輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842..., 
     由于回傳型別是整數，小數部分將被舍去，

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while(l < r){
            int mid = l + (long long)r + 1>> 1;
            if(mid <= x/mid) l = mid;  // 查找t^2 <= x
            else r = mid - 1;
        }
        return l;
    }
};

35. 搜索插入位置

給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，

你可以假設陣列中無重復元素，

示例 :

輸入: [1,3,5,6], 5
輸出: 2

輸入: [1,3,5,6], 2
輸出: 1

輸入: [1,3,5,6], 7
輸出: 4

輸入: [1,3,5,6], 0
輸出: 0

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty() || target > nums.back()) return nums.size();
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;  // 查找t>=x的第一個數
            else l = mid + 1; 
        }
        return l;
    }
};

34. 在排序陣列中查找元素的第一個和最后一個位置

給定一個按照升序排列的整數陣列 nums，和一個目標值 target，找出給定目標值在陣列中的開始位置和結束位置，

你的演算法時間復雜度必須是 O(log n) 級別，

如果陣列中不存在目標值，回傳 [-1, -1]，

示例 :

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

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

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return {-1, -1};
        return {getFirst(nums, target), getLast(nums, target)};
    }
    int getFirst(vector<int>& nums, int target){
        int l = 0, r = nums.size()-1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return nums[l] != target ? -1 : l;
    }
    int getLast(vector<int>& nums, int target){
        int l = 0, r = nums.size()-1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return nums[l] != target ? -1 : l;
    }
};

74. 搜索二維矩陣

撰寫一個高效的演算法來判斷 m x n 矩陣中，是否存在一個目標值，該矩陣具有如下特性：

每行中的整數從左到右按升序排列，
每行的第一個整數大于前一行的最后一個整數，

示例 ：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
輸出：true

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
輸出：false

輸入：matrix = [], target = 0
輸出：false

注：二維陣列下標轉換

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n*m-1;
        while(l < r){
            int mid = l + r >> 1;
            if(matrix[mid/m][mid%m] >= target) r = mid;  // t>=x
            else l = mid + 1; 
        }
        return matrix[l/m][l%m] == target ? true : false;
    }
};

153. 尋找旋轉排序陣列中的最小值

假設按照升序排序的陣列在預先未知的某個點上進行了旋轉，

( 例如，陣列 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )，

請找出其中最小的元素，

你可以假設陣列中不存在重復元素，

示例 :

輸入: [3,4,5,1,2]
輸出: 1

輸入: [4,5,6,7,0,1,2]
輸出: 0

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] <= nums.back()) r = mid;  // nums[t]<=nums.back
            else l = mid + 1;
        }
        return nums[l]; 
    }
};

33. 搜索旋轉排序陣列

給你一個升序排列的整數陣列 nums ，和一個整數 target ，

假設按照升序排序的陣列在預先未知的某個點上進行了旋轉，（例如，陣列 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] ），

請你在陣列中搜索 target ，如果陣列中存在這個目標值，則回傳它的索引，否則回傳 -1 ，

示例 ：

輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4

輸入：nums = [4,5,6,7,0,1,2], target = 3
輸出：-1

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

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        // 找到最小值
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] <= nums.back()) r = mid;  // nums[t] <= nums.back()
            else l = mid + 1;
        }
        if(target <= nums.back()) r = nums.size() - 1;
        else l = 0, r--;
        // 單調二分
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;  // t >= x
            else l = mid + 1;
        }
        return nums[l] == target ? l : -1;
    }
};

278. 第一個錯誤的版本

你是產品經理，目前正在帶領一個團隊開發新的產品，不幸的是，你的產品的最新版本沒有通過質量檢測，由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的，

假設你有 n 個版本 [1, 2, …, n]，你想找出導致之后所有版本出錯的第一個錯誤的版本，

你可以通過呼叫 bool isBadVersion(version) 介面來判斷版本號 version 是否在單元測驗中出錯，實作一個函式來查找第一個錯誤的版本，你應該盡量減少對呼叫 API 的次數，

示例:

給定 n = 5，并且 version = 4 是第一個錯誤的版本，

呼叫 isBadVersion(3) -> false
呼叫 isBadVersion(5) -> true
呼叫 isBadVersion(4) -> true

所以，4 是第一個錯誤的版本， 

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while(l < r){
            int mid = l + (long long)r >> 1;  // n為最大整數，溢位
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1; 
        }
        return l;
    }
};

162. 尋找峰值

峰值元素是指其值大于左右相鄰值的元素，

給定一個輸入陣列 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并回傳其索引，

陣列可能包含多個峰值，在這種情況下，回傳任何一個峰值所在位置即可，

你可以假設 nums[-1] = nums[n] = -∞，

示例 :

輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素，你的函式應該回傳其索引 2，

輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5 
解釋: 你的函式可以回傳索引 1，其峰值元素為 2；
     或者回傳索引 5， 其峰值元素為 6，
說明:
你的解法應該是 O(logN) 時間復雜度的，

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[mid + 1]) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

287. 尋找重復數

給定一個包含 n + 1 個整數的陣列 nums，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數，假設只有一個重復的整數，找出這個重復的數，

示例 :

輸入: [1,3,4,2,2]
輸出: 2

輸入: [3,1,3,4,2]
輸出: 3
說明：
不能更改原陣列（假設陣列是只讀的），
只能使用額外的 O(1) 的空間，
時間復雜度小于 O(n2) ，
陣列中只有一個重復的數字，但它可能不止重復出現一次，

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size()-1;
        int l = 1, r = n;
        while(l < r){
            int cnt = 0;
            int mid = l + r >> 1;
            for(int x : nums)
                if(x <= mid) cnt++;  // 統計中位數及左邊數字的個數
            if(cnt > mid) r = mid;
            else l = mid+1; 
        }
        return l;
    }
};

275. H 指數 II

給定一位研究者論文被參考次數的陣列（被參考次數是非負整數），陣列已經按照 升序排列 ，撰寫一個方法，計算出研究者的 h 指數，

h 指數的定義: “h 代表“高參考次數”（high citations），一名科研人員的 h 指數是指他（她）的 （N 篇論文中）總共有 h 篇論文分別被參考了至少 h 次，（其余的 N - h 篇論文每篇被參考次數不多于 h 次，）"

示例:

輸入: citations = [0,1,3,5,6]
輸出: 3 
解釋: 給定陣串列示研究者總共有 5 篇論文，每篇論文相應的被參考了 0, 1, 3, 5, 6 次，
     由于研究者有 3 篇論文每篇至少被參考了 3 次，其余兩篇論文每篇被參考不多于 3 次，所以她的 h 指數是 3，

說明:
如果 h 有多有種可能的值 ，h 指數是其中最大的那個，

思路：

• 至少存在h個數≥h
  即看倒數第h個數是否≥h

class Solution {
public:
    int hIndex(vector<int>& nums) {
        int l = 0, r = nums.size();
        while(l < r){
            int mid = l + r + 1>> 1;
            if(nums[nums.size() - mid] >= mid) l = mid;  // 左邊都滿足nums[h]>=h,判斷倒數第h個數是否≥h
            else r = mid - 1;
        }
        return l;
    }
};

參考鏈接：

• https://blog.csdn.net/zhanly19/article/details/108999734
• https://www.bilibili.com/video/BV1Ft41157zW

擴展分類

練習題

題型一：在陣列中查找符合條件的元素的下標
一般而言這個陣列是有序的，也可能是半有序的（旋轉有序陣列或者山脈陣列），

題型二：在一個有范圍的區間里搜索一個整數
定位一個有范圍的整數，這件事情也叫「二分答案」或者叫「二分結果」，如果題目要求的是一個整數，這個整數有明確的范圍，可以考慮使用二分查找，

題型三：復雜的二分查找問題（判別條件需要遍歷陣列）
「力扣」上還有這樣一類問題：目標變數和另一個變數有相關關系（一般而言是線性關系），目標變數的性質不好推測，但是另一個變數的性質相對容易推測（滿足某種意義上的單調性），這樣的問題的判別函式通常會寫成一個函式的形式，

這一類問題可以統稱為「 最大值極小化 」問題，最原始的問題場景是木棍切割問題，這道題的原始問題是「力扣」第 410 題，

解題的思路是這樣的：

• 分析出題目要我們找一個整數，這個整數有范圍，所以可以用二分查找；
• 分析出單調性，一般來說是一個變數 a 的值大了，另一個變數 b 的值就變小，而「另一個變數的值」 b 有限制，因此可以通過調整 a 的值達到控制 b 的效果；
• 這一類問題的題目條件一定會給出 連續、正整數 這樣的關鍵字，如果沒有，問題場景也一定蘊含了這兩個關鍵資訊，

以下給出的問題無一例外，

LeetBook總結

• 704. 二分查找(簡單)

  class Solution {
  public:
      int search(vector<int>& nums, int target) {
          if(nums.empty()) return -1;
          int l = 0, r = nums.size() - 1;
          while(l < r){
              int mid = l + r >> 1;
              if(nums[mid] >= target) r = mid;
              else l = mid + 1;
          }
          return nums[l] == target ? l : -1; 
      }
  };
  

• 374. 猜數字大小

  /** 
   * Forward declaration of guess API.
   * @param  num   your guess
   * @return 	     -1 if num is lower than the guess number
   *			      1 if num is higher than the guess number
   *               otherwise return 0
   * int guess(int num);
   */
  
  class Solution {
  public:
      int guessNumber(int n) {
          int l = 1, r = n;
          while(l < r){
              int mid = l + (long long)r >> 1;
              int res = guess(mid);
              if(res <= 0) r = mid;
              else l = mid + 1;
          }
          return l;
      }
  };
  

• 81. 搜索旋轉排序陣列 II(中等)
  【分析】與lc33類似，多了重復數字的情況，只需去掉旋轉陣列結尾和開頭相同的部分，剩下的與lc33完全相同，

  class Solution {
  public:
      bool search(vector<int>& nums, int target) {
          if(nums.empty()) return false;
          // 去掉結尾和開頭相同的部分
          int t = nums.size() - 1;
          while(t > 0 && nums[t] == nums[0]) t--;
          // 找最小值
          int l = 0, r = t;
          while(l < r){
              int mid = l + r >> 1;
              if(nums[mid] <= nums[t]) r = mid;
              else l = mid + 1;
          }
          if(target <= nums[t]) r = t;  // 答案在右邊
          else l = 0, r--;  // 答案在左邊
          // 單調二分
          while(l < r){
              int mid = l + r >> 1;
              if(nums[mid] >= target) r = mid;
              else l = mid + 1;
          }
          return nums[l] == target;
      }
  };
  

• 154. 尋找旋轉排序陣列中的最小值 II(中等)

  【分析】與lc153類似，多了重復數字的情況，只需去掉旋轉陣列結尾和開頭相同的部分，剩下的與lc153完全相同，

  class Solution {
  public:
      int findMin(vector<int>& nums) {
          int t = nums.size()-1;
          while(t > 0 && nums[t] == nums[0]) t--;  // 去掉結尾與開頭相同的部分
          int l = 0, r = t;
          while(l < r){
              int mid = l + r >> 1;
              if(nums[mid] <= nums[t]) r = mid;
              else l = mid + 1;
          }
          return nums[l];
      }
  };
  

• 852. 山脈陣列的峰頂索引（簡單）

  【思路】找峰頂，判斷是否有 M ≥ M+1

  class Solution {
  public:
      int peakIndexInMountainArray(vector<int>& nums) {
          int l = 0, r = nums.size() - 1;
          while(l < r){
              int mid = l + r >> 1;
              if(nums[mid] >= nums[mid+1]) r = mid;  // M >= M+1
              else l = mid + 1;
          }
          return l;
      }
  };
  

• 1095. 山脈陣列中查找目標值（中等）

  【思路】先找到峰頂，左右區間找target

    /**
     * // This is the MountainArray's API interface.
     * // You should not implement it, or speculate about its implementation
     * class MountainArray {
     *   public:
     *     int get(int index);
     *     int length();
     * };
     */
    
    class Solution {
    public:
        int findInMountainArray(int target, MountainArray &nums) {
            // 找到峰頂，最大值
            int l = 0, r = nums.length() - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(nums.get(mid) >= nums.get(mid+1)) r = mid;
                else l = mid + 1;
            }
            int t = l;  // t為峰頂
            // 在左側遞增區間找target
            l = 0, r = t;
            while(l < r){
                int mid = l + r >> 1;
                if(nums.get(mid) >= target) r = mid;
                else l = mid + 1; 
            }
            if(nums.get(l) == target) return l;
            // 在右側遞減區間找target
            l = t + 1, r = nums.length() - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(nums.get(mid) <= target) r = mid;
                else l = mid + 1;
            }
            if(nums.get(l) == target) return l;
            else return -1;
        }
    };
  

• 658. 找到 K 個最接近的元素（中等）

  【思路】只尋找左邊界即可，

  假設 mid 是左邊界，則當前區間覆寫的范圍是 [mid, mid + k -1]. 如果發現 a[mid] 與 x 距離比 a[mid + k] 與 x 的距離要大，說明解一定在右側，否則在左側，

  class Solution {
  public:
      vector<int> findClosestElements(vector<int>& nums, int k, int x) {
          int l = 0, r = nums.size() - k;  // 保證mid+k不超出范圍
          while(l < r){
              int mid = l + r >> 1;
              if(x - nums[mid] <= nums[mid+k] - x) r = mid;
              else l = mid + 1; 
          }
          return vector<int>(nums.begin()+l, nums.begin()+l+k);
      }
  };
  

• 1300. 轉變陣列后最接近目標值的陣列和
  【思路】二分查找確定這個整數值（閾值越大，轉變陣列和越大，具有單調性，可用二分，對比lc658）
  如果選擇一個閾值 value ，使得它對應的 sum 是第 1 個大于等于 target 的，那么目標值可能在 value 也可能在 value - 1
  

   class Solution {
   public:
       int findBestValue(vector<int>& arr, int target) {
           int l = 0, r = 0;
           for(int num : arr)
               r = max(r, num);  // 找陣列中的最大值作為右邊界
           // 二分找到第一個大于等于target的閾值val
           while(l < r){  
               int mid = l + r >> 1;
               int sum = calSum(arr, mid);
               if(sum >= target) r = mid;
               else l = mid + 1;
           }
           // 找最接近target左右兩邊最小的數
           int sum1 = calSum(arr, l - 1);
           int sum2 = calSum(arr, l);
           if(target - sum1 <= sum2 - target)  // k-x1 <= x2-k
               return l - 1;
           return l;
       }
       int calSum(vector<int>& arr, int val){  // 計算轉變陣列的和
           int sum = 0;
           for(int num : arr)
               sum += min(num, val);
           return sum;
       }
   };