首页Coding

# LeetCode 278. 第一个错误的版本

LeetCode 278

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n] ，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
    调用 isBadVersion(3) -> false 
    调用 isBadVersion(5) -> true 
    调用 isBadVersion(4) -> true
    所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

提示：

  • 1≤1 \le bad ≤\le n ≤231−1\le 2^{31} - 1

# Method: 二分查找

注意到一个性质：当一个版本为正确版本，则该版本之前的所有版本均为正确版本；当一个版本为错误版本，则该版本之后的所有版本均为错误版本

将左右边界分别初始化为 1 和 n ，其中 n 是给定的版本数量。设定左右边界之后，每次我们都依据左右边界找到其中间的版本，检查其是否为正确版本。如果该版本为正确版本，那么第一个错误的版本必然位于该版本的右侧，我们缩紧左边界；否则第一个错误的版本必然位于该版本及该版本的左侧，我们缩紧右边界

这样我们每判断一次都可以缩紧一次边界，而每次缩紧时两边界距离将变为原来的一半，因此我们至多只需要缩紧 O(logn) 次

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)O(\log{n})，其中 n 是给定版本的数量

空间复杂度：O(1)O(1)。我们只需要常数的空间保存若干变量

# LeetCode 33. 搜索旋转排序数组

33. Search in Rotated Sorted Array

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前， nums 在预先未知的某个下标 k （ 0 <= k < nums.length ）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] （下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log⁡n)O(\log{n}) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1≤1 \le nums.length ≤5000\le 5000
  • −104≤-10^4 \le nums[i] ≤104\le 10^4
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • −104≤-10^4 \le target ≤104\le 10^4

# Method: 二分查找

算法思路：在经过旋转后，数组 nums 可以分成两个有序的子数组，可首先找出这两个子数组的分界线，然后将 target 与子数组端点的大小进行比较，从而确定在哪个子数组中查找 target

其中，确定两个子数组的分界线、在某一个子数组中查找 target ，这两步都可以通过二分查找算法实现

代码实现：

int search(vector<int>& nums, int target) {
    int n = nums.size();
    if (n == 1) return nums[0] == target ? 0 : -1;
    
    // 二分查找，寻找数组 nums 的分界线
    int l = 0;
    int r = n - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (nums[mid] >= nums[0]) l = mid;
        else r = mid - 1;
    }
    // 确定搜索区间
    if (target == nums[0]) return 0;
    else if (target > nums[0]) l = 0; // 上一次二分查找结束时，l == r
    else if (target < nums[0]) {
        l = l + 1;
        r = n - 1;
    }
    // 二分查找，确定 target 的位置
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else if (nums[mid] > target) r = mid - 1;
    }
    return -1;
}
# LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置


LeetCode 34. Find First and Last Position of Element in Sorted Array


给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。


如果数组中不存在目标值 target，返回 [-1, -1]。


你必须设计并实现时间复杂度为 O(log⁡n)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]



提示：


    

  • 0≤0 \le  nums.length  ≤105\le 10^5
    • 

  • −109≤-10^9 \le  nums[i]  ≤109\le 10^9
    • 

  • nums  是一个非递减数组
    • 

  • $- 10^9 \le $  target  ≤109\le 10^9
    • 



# Method 1: while (left < right)


// 寻找元素的第一个位置（找出第一个大于等于 target 的元素）
int LowerBoundSearch(vector<int> nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l < r) { // 注意：循环结束时 l = r
        int mid = l + ((r - l) >> 1);
        if (nums[mid] >= target)            //lower bound 一定在区间 [l, mid]
            r = mid;
        else if (nums[mid] < target)        //lower bound 一定在区间 (mid, r]
            l = mid + 1;
    }
    if (nums[l] == target)
        return l;
    else
        return -1;
}
// 寻找元素的最后一个位置（找出最后一个小于等于 target 的元素）
int UpperBoundSearch(vector<int> nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + ((r - l + 1) >> 1);   // 避免陷入死循环，mid 向上取整
        if (nums[mid] <= target)            //upper bound 一定在区间 [mid, r]
            l = mid;
        else if (nums[mid] > target)        //upper bound 一定在区间 [l, mid)
            r = mid - 1;
    }
    if (nums[r] == target)
        return r;
    else
        return -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
    int n = nums.size();
    if (n == 0) {   // 空数组
        vector<int> ans = {-1,-1};
        return ans;
    }
    int lb = LowerBoundSearch(nums, target);
    int ub = UpperBoundSearch(nums, target);
    vector<int> ans = {lb,ub};
    return ans;
}
# Method 2: while (left <= right)


// 寻找元素的第一个位置
int LowerBoundSearch(vector<int> nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) { // 注意：循环结束时 l = r + 1
        int mid = l + ((r - l) >> 1);
        if (nums[mid] >= target)
            r = mid - 1;             // 注意：循环结束时， l 刚好就是 lower bound
        else if (nums[mid] < target)
            l = mid + 1;
    }
    if (nums[l] == target)
        return l;
    else
        return -1;
}
// 寻找元素的最后一个位置
int UpperBoundSearch(vector<int> nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) { // 注意：循环结束时 l = r + 1
        int mid = l + ((r - l) >> 1);
        if (nums[mid] <= target)
            l = mid + 1;
        else if (nums[mid] > target)
            r = mid - 1;            // 注意：循环结束时， r 刚好是 upper bound
    }
    if (nums[r] == target)
        return r;
    else
        return -1;
}
# LeetCode 35. 搜索插入位置


LeetCode 35. Search Insert Position


给定一个排序数组 nums 和一个目标值 target，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。


请必须使用时间复杂度为 O(log⁡n)O(\log n) 的算法。




示例 1：


输入：nums = [1,3,5,6], target = 5
输出：2



示例 2：


输入：nums = [1,3,5,6], target = 2
输出：1



示例 3：


输入：nums = [1,3,5,6], target = 7
输出：4



提示：


    

  • 1≤1 \le nums.length ≤104\le 10^4
    • 

  • −104≤-10^4 \le nums[i] ≤104\le 10^4
    • 

  • nums 为 无重复元素 的 升序 排列数组
    • 

  • −104≤-10^4 \le target ≤104\le 10^4
    • 



# Method: 二分查找


在一个有序数组中找到第一个大于等于  target  的下标


int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    };
    return left;
}
二分查找需要注意边界条件，比如：循环结束条件中  left  和  right  的关系，更新  left  和  right  位置时要不要加 1 减 1。


写对二分查找不是套模板并往里面填空，需要仔细分析题意


# LeetCode 4. 寻找两个正序数组的中位数


4. Median of Two Sorted Arrays


给定两个大小分别为 m 和 n 的正序（从小到大）数组  nums1  和  nums2 。请你找出并返回这两个正序数组的 中位数 。


算法的时间复杂度应该为 O(log⁡(m+n))O(\log{(m + n)})。


示例 1：


输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2



示例 2：


输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5



提示：


    

  • nums1.length == m
    • 

  • nums2.length == n
    • 

  • 0≤0 \le  m  ≤1000\le 1000
    • 

  • 0≤0 \le  n  ≤1000\le 1000
    • 

  • 1≤1 \le  m + n  ≤2000\le 2000
    • 

  • −106≤- 10^6 \le  nums1[i] ,  nums2[i]  ≤106\le 10^6
    • 



# 思路


当 m+nm + n 为奇数时，中位数即为两个数组中的第 (m+n)/2(m + n) / 2 个元素；当 m+nm + n 为偶数时，中位数应为第 (m+n)/2(m + n) / 2 个元素与第 (m+n)/2+1(m + n) / 2 + 1 个元素的平均值


因此，本题相当于要在两个有序数组中找出第 kk 小的数，其中，kk 取 (m+n)/2(m + n) / 2 或 (m+n)/2+1(m + n) / 2 + 1


# Method: 二分查找


算法思路：


为找出第 kk 小的数，可比较  nums1[k / 2 - 1]  和  nums2[k / 2 - 1]  ：


    

  • 若  nums1[k / 2 - 1] <= nums2[k / 2 - 1]  ，则最多有  nums1[0, k / 2 - 2]  和  nums2[0, k / 2 - 2]  （一共 k−2k - 2 个数）小于  nums1[k / 2 - 1]  ，即， nums1[k / 2 - 1]  不可能是第 kk 小的数， nums1[0, k / 2 - 2]  更不可能是第 kk 小的数，因此，可排除  nums1[0, k / 2 - 1]
    • 

  • 若  nums1[k / 2 - 1] > nums2[k / 2 - 1]  ，类似地，则可排除  nums2[0, k / 2 - 1]
    • 



此时，已经排除了 k/2k / 2 个数，接下来，可以在剩余元素中继续进行二分查找，并根据排除数的个数，更新 kk 的值




在代码实现中，我们用  start1  和  start2  分别表示  nums1  和  nums2  中的待考察元素的起点




有以下三种边界情况：


    

  • 如果一个数组为空，即，该数组中的所有元素都被排除，此时，可以直接返回另一个数组中第 kk 小的元素
    • 

  • 如果  nums1[k / 2 - 1]  或者  nums2[k / 2 - 1]  越界，我们可以选取对应数组的最后一个元素。此时，须根据排除数的个数来更新 kk ，而不能直接将 kk 减去 k/2k / 2
    • 

  • 如果 k=1k = 1 ，返回两个数组首元素的最小值即可
    • 



代码实现：


// 在 nums1 [start1, :] 和 nums2 [start2, :] 中寻找第 k 小的数
int getKthElement(vector<int>& nums1, int start1, vector<int>& nums2, int start2, int k) {
    int m = nums1.size();
    int n = nums2.size();
    if (start1 == m) return nums2[start2 + k - 1]; //nums1 元素已全部排除
    if (start2 == n) return nums1[start1 + k - 1]; //nums2 元素已全部排除
    if (k == 1) return min(nums1[start1], nums2[start2]);
    int index1 = min(start1 + k / 2 - 1, m - 1); //nums1 中的第 k / 2 个剩余元素
    int index2 = min(start2 + k / 2 - 1, n - 1); //nums2 中的第 k / 2 个剩余元素
    if (nums1[index1] <= nums2[index2]) { // 排除 nums [start1, index1]
        k = k - (index1 - start1 + 1);    // 更新 k
        return getKthElement(nums1, index1 + 1, nums2, start2, k); // 递归，继续在剩余元素中查找
    } else {                              // 排除 nums2 [start2, index2]
        k = k - (index2 - start2 + 1);    // 更新 k
        return getKthElement(nums1, start1, nums2, index2 + 1, k); // 递归，继续在剩余元素中查找
    }
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int len = nums1.size() + nums2.size();
    if (len % 2 == 1) { //m + n 为奇数
        return getKthElement(nums1, 0, nums2, 0, len / 2 + 1);      // 第 (m + n) / 2 + 1 个小的数
    } else {            //m + n 为偶数
        int temp1 = getKthElement(nums1, 0, nums2, 0, len / 2);     // 第 (m + n) / 2 个小的数
        int temp2 = getKthElement(nums1, 0, nums2, 0, len / 2 + 1);
        return (temp1 + temp2) / 2.0;
    }
}
时间复杂度：O(log⁡(m+n))O(\log{(m + n)})，每次抵归将查找范围减少一半，因此，时间复杂度为 log⁡k\log k ，其中，kk 取 (m+n)/2(m + n) / 2 或 (m+n)/2+1(m + n) / 2 + 1


空间复杂度：O(1)O(1)


参考：



# LeetCode 69. x 的平方根


LeetCode 69. Sqrt(x)


给你一个非负整数  x  ，计算并返回  x  的 算术平方根 。


由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。


注意：不允许使用任何内置指数函数和算符，例如  pow(x, 0.5)  或者  x ** 0.5  。


示例 1：


输入：x = 4
输出：2



示例 2：


输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。



提示：


    

  • 0≤0 \le  x  ≤231−1\le 2^{31} - 1
    • 



# Method: 二分查找


找到满足  k*k <= x  的最大整数  k


int mySqrt(int x) {
    int left = 0, right = x;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if ((long long) mid * mid <= x)
            left = mid + 1;
        else
            right = mid - 1;
    };
    return right;
}
其中， (long long)  强制转换类型，避免 mid * mid  溢出


或，考虑  mid <= x / mid （此时需另外分析  mid == 0  的情形）


int mySqrt(int x) {
    int left = 0, right = x;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (mid == 0)
            break;
        else if (mid <= (x / mid))
            left = mid + 1;
        else
            right = mid - 1;
    };
    return right;
}
# LeetCode 744. 寻找比目标字母大的最小字母


LeetCode 744. Find Smallest Letter Greater Than Target


给你一个字符数组  letters  ，该数组按非递减顺序排序，以及一个字符  target  。 letters  里至少有两个不同的字符。


返回  letters  中大于  target  的最小的字符。如果不存在这样的字符，则返回  letters  的第一个字符。


示例 1：


输入：letters = ["c","f","j"], target = "a"
输出："c"
解释：letters 中字典上比 'a' 大的最小字符是 'c'



示例 2：


输入：letters = ["c","f","j"], target = "c"
输出："f"
解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'



示例 3：


输入：letters = ["c","f","j"], target = "d"
输出："f"
解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]



示例 4:


输入：letters = ["c","f","j"], target = "z"
输出："c"



提示：


    

  • 2≤2 \le  letters.length  ≤104\le 10^4
    • 

  • letters[i]  是一个小写字母
    • 

  • letters  按非递减顺序排序
    • 

  • letters  最少包含两个不同的字母
    • 

  • target  是一个小写字母
    • 



# Method: 二分查找


旨在找出大于  target  的最小字母，可以考虑二分查找算法


二分查找的基本思路：


    

  1. 考虑  while  循环终止条件为  left = right

      

    • 如果  letters[mid] > target  ，则所求字母在  [left, mid]  区间，所以更新  right = mid
      • 

    • 如果  letters[mid] <= target ，则所求字母在  [mid + 1, right]  区间，所以更新  left = mid + 1
      • 

    

    2. 

  2. 循环结束时，需要判断  letters[left]  是否大于  target

      

    • 若是，输出  letters[left]
      • 

    • 若否，则所有元素均不大于  target  ，输出  letters[0]
      • 

    

    3. 



// 找出大于目标值的最小元素索引
int LowerBoundSearch(vector<char> letters, char target) {
    int left = 0, right = letters.size() - 1;
    while (left < right) {
        int mid = left + ((right - left) >> 1); // 注意：+ 号优先级高于位运算 >> ，需要将 (right - left) >> 1 括起来
        if (letters[mid] > target)
            right = mid;
        else
            left = mid + 1;
    }
    // 判断 letters [left] 是否大于 target
    if (letters[left] > target)
        return left;
    else  // 所有字母都比 target 小（注意：字母在 letters 中依序循环出现，返回 0 ）
        return 0;
    //// 等价于
    // return letters[left] > target ? left : 0;
}
char nextGreatestLetter(vector<char>& letters, char target) {
    int index = LowerBoundSearch(letters, target);
    return letters[index];
}