算法总结 DAY_05

二分专题

复杂度log(n)：二分法的”代言词“

二分模板：

int l = 0;
      int r = nums.size() - 1;
      int mid;
      while(l <= r){      // 另一种模板 l <r
          mid = l + (r - l) / 2;  //左中点
          if(target == nums[mid])
              return mid;
          if(target < nums[mid])
              r = mid - 1;
          if(target > nums[mid])
              l = mid + 1;    
      }
      return l;

详细讲解文章链接：

关于二分法三个模板更详细的说明

第一个错误的版本

LeetCode 278. first-bad-version

题目：

题解

二分法

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

class Solution {
public:
    int firstBadVersion(int n) {
        int ans = 0;
        int l = 1;
        int r = n;
        int mid;
        while(l <= r){
            mid = l + (r - l) / 2;
            if(isBadVersion(mid)){
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;    
        }   
        return ans;
    }
};

官方题解：

用了另一种二分模板

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
};

复杂度分析

时间复杂度：O(log n)，其中 n是给定版本的数量。
空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

寻找旋转排序数组中的最小值

LeetCode 153. find-minimum-in-rotated-sorted-array

题目：

题解

二分法

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

官方题解：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            }
            else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
};

复杂度分析

时间复杂度：时间复杂度为 O(logn)，其中 n 是数组 nums 的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为 O(logn)。
空间复杂度：O(1)。

H 指数 II

LeetCode 153. h-index-ii

题目：

题解

二分法

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int l = 0;
        int n = citations.size();
        int r = n - 1;
        int mid;
        while(l <= r){
            mid = l + (r - l) / 2;
            if(n - mid > citations[mid])
                l = mid + 1; 
            if(n - mid <= citations[mid])
                r = mid - 1;
                   
        }
        return n - l;
    }
};

复杂度分析

时间复杂度：O(logn)，其中 n 为数组 citations 的长度。二分查找的时间复杂度为 O(logn)。
空间复杂度：O(1)。

寻找峰值

LeetCode 162. find-peak-element

题目：

题解

二分法

思路与算法

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        int mid;
        if(r == 0)
            return 0;
        if(r == 1)
            return nums[0] > nums[1] ? 0 : 1;
        while(l <= r){
            mid = l + (r - l) / 2;
            if(mid != 0 && mid != (nums.size()-1)){
                if(nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1])
                    return mid;
                if(nums[mid-1] > nums[mid] && nums[mid] > nums[mid+1])
                    r = mid - 1; 
                if(nums[mid+1] > nums[mid] && nums[mid] > nums[mid-1])
                    l = mid + 1;  
                if(nums[mid+1] > nums[mid] && nums[mid] < nums[mid-1]) 
                    // 两边都大（位于山谷） 默认朝右走
                    l = mid + 1;
            }
            else{
                if(mid == 0){
                    if(nums[mid] > nums[mid+1])
                        return mid;
                    else
                        l = mid + 1;
                } 
                if(mid == (nums.size()-1)){
                    if(nums[mid] > nums[mid-1])
                        return mid;
                    else
                        r = mid - 1;
                } 
            }
        }
        return -1;
    }
};

官方题解：

差别在于官方题解将边界情况用另一个函数分析

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();

        // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
        // 方便处理 nums[-1] 以及 nums[n] 的边界情况
        auto get = [&](int i) -> pair<int, int> {
            if (i == -1 || i == n) {
                return {0, 0};
            }
            return {1, nums[i]};
        };

        int left = 0, right = n - 1, ans = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (get(mid - 1) < get(mid) && get(mid) > get(mid + 1)) {
                ans = mid;
                break;
            }
            if (get(mid) < get(mid + 1)) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return ans;
    }
};