首页 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)

参考：

  • 力扣官方题解
  • windliang

# 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. 循环结束时，需要判断 letters[left] 是否大于 target
    • 若是，输出 letters[left]
    • 若否，则所有元素均不大于 target ，输出 letters[0]
// 找出大于目标值的最小元素索引
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];
}
阅读次数 次