LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 合并两个有序数组的时间复杂度是 O(m + n)，不满足题目要求的 O(log(m + n))

class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    vector<double> v;
    merge(begin(nums1), end(nums1), begin(nums2), end(nums2), back_inserter(v));
    int n = size(v);
    return (v[(n - 1) / 2] + v[n / 2]) / 2.0;
  }
};

• 因此不能合并数组。有序数组、O(log(m + n))，这两点显然提示的是使用二分查找
• 二分查找两个有序范围中第 k(k > 0) 小的元素，每次要缩小 k/2 的范围。设两个有序范围为 A 和 B，先查找两个范围中第 k/2 小的数，即 m1 = A[k / 2 - 1] 和 m2 = B[k / 2 - 1]，如果 m1 < m2，则说明 A 的前 k / 2 个元素都不会是第 k 小的元素

假设操场上的学生排成两列队伍，两列队伍都是身高由矮到高排列
现在要从所有人中找出第 6 矮的学生，各抽出前 3 名学生，编号如下：

123###############  // 队伍 A
456###############  // 队伍 B

如果 3 比 6 矮，则第 6 矮的不会在 123 中，证明如下：
假设 3 是第 6 矮，则要有 5 个更矮的，12 两个，差 3 个
6 比 3 高，3 和 6 之后都是更高的，6 之前只有 2 个，不可能满足条件
同理，既然 3 不可能是第 6 矮，3 之前的更不可能

• 因此如果 m1 < m2，则目标值在 m1 的右侧 和 B 中（反之则反），这样即可缩小范围

A 0 2 3 5 6 9
B 1 4 7 8

以k = 6 为例，第 6 小的元素为 5，如何二分查找到它？

k = 6 => k / 2 = 3
m1 = 3  // A范围的第 3 个元素
m2 = 7  // B范围的第 3 个元素
m1 < m2 => 排除 A 左侧 3 个元素

A 5 6 9
B 1 4 7 8

查找剩余范围第 3 小的元素（已排除 3 个）
k = 3 => k / 2 = 1
m1 = 5  // A 范围的第 1 个元素
m2 = 1  // B 范围的第 1 个元素
m1 > m2 => 排除 B 左侧 1 个元素

查找剩余范围第 2 小的元素（已排除 4 个）
A 5 6 9
B 4 7 8
k = 2 => k / 2 = 1
m1 = 5  // A 范围的第 1 个元素
m2 = 4  // B 范围的第 1 个元素
m1 > m2 => 排除 B 左侧 1 个元素

查找剩余范围第 1 小的元素（已排除 5 个）
A 5 6 9
B 7 8
显然取两者较小的首元素即可

• 如果一个范围连 k / 2 个元素都没有，则从元素数更多的那队排除

12                  // 队伍 A（只有 2 个人，抽不出 3 个）
456###############  // 队伍 B

要找第 6 矮，12 可能是，但 456 不可能是，排除 456

• 解法如下

class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (empty(nums1) && empty(nums2)) {
      return 0;
    }
    int n = size(nums1) + size(nums2);
    if (n % 2 & 1) {
      return findK(nums1, nums2, 0, 0, (n + 1) / 2);
    }
    double x = findK(nums1, nums2, 0, 0, n / 2);
    double y = findK(nums1, nums2, 0, 0, n / 2 + 1);
    return (x + y) / 2.0;
  }

  // 查找 nums1 和 nums2 中第 k 小的值
  // a 为 nums1 查找范围的起点，b 为 nums2 查找范围的起点
  double findK(vector<int>& nums1, vector<int>& nums2, int a, int b, int k) {
    if (a >= size(nums1)) {     // nums1 越界
      return nums2[b + k - 1];  // nums2 中从 b 开始第 k 小的数即为结果
    }
    if (b >= size(nums2)) {     // nums2 越界
      return nums1[a + k - 1];  // nums2 中从 b 开始第 k 小的数即为结果
    }
    if (k == 1) {  // k 为 1 则直接取较小的首元素
      return min(nums1[a], nums2[b]);
    }
    int x = a + k / 2 - 1;  // 下列的 x + 1 - a 实际就是 k / 2
    int y = b + k / 2 - 1;  // 下列的 y + 1 - b 实际就是 k / 2
    if (x >= size(nums1)) {  // nums1 不够 k / 2 个元素，从 nums2 排除元素
      return findK(nums1, nums2, a, y + 1, k - (y + 1 - b));
    }
    if (y >= size(nums2)) {  // nums2 不够 k / 2 个元素，从 nums1 排除元素
      return findK(nums1, nums2, x + 1, b, k - (x + 1 - a));
    }
    if (nums1[x] <= nums2[y]) {  // num1 的较小，从 nums1 排除元素
      return findK(nums1, nums2, x + 1, b, k - (x + 1 - a));
    }
    // nums2 的较小，从 nums2 排除元素
    return findK(nums1, nums2, a, y + 1, k - (y + 1 - b));
  }
};

• 对上述代码进行一些化简，可以直接取第 (n + 1) / 2 小和第 (n + 2) / 2 小的两个数的平均值，如果 n 为奇数则两者为相同值

class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int n = size(nums1) + size(nums2);
    int x = (n + 1) / 2;
    int y = (n + 2) / 2;
    return (findK(nums1, nums2, 0, 0, x) + findK(nums1, nums2, 0, 0, y)) / 2.0;
  }

  // 查找 nums1 和 nums2 中第 k 小的值
  // a 为 nums1 查找范围的起点，b 为 nums2 查找范围的起点
  double findK(vector<int>& nums1, vector<int>& nums2, int a, int b, int k) {
    if (a >= size(nums1)) {     // nums1 越界
      return nums2[b + k - 1];  // nums2 中从 b 开始第 k 小的数即为结果
    }
    if (b >= size(nums2)) {     // nums2 越界
      return nums1[a + k - 1];  // nums2 中从 b 开始第 k 小的数即为结果
    }
    if (k == 1) {  // k 为 1 则直接取较小的首元素
      return min(nums1[a], nums2[b]);
    }
    int x = a + k / 2 - 1;
    int y = b + k / 2 - 1;
    if (x >= size(nums1)) {  // nums1 不够 k / 2 个元素，从 nums2 排除元素
      return findK(nums1, nums2, a, y + 1, k - k / 2);
    }
    if (y >= size(nums2)) {  // nums2 不够 k / 2 个元素，从 nums1 排除元素
      return findK(nums1, nums2, x + 1, b, k - k / 2);
    }
    if (nums1[x] <= nums2[y]) {  // num1 的较小，从 nums1 排除元素
      return findK(nums1, nums2, x + 1, b, k - k / 2);
    }
    // nums2 的较小，从 nums2 排除元素
    return findK(nums1, nums2, a, y + 1, k - k / 2);
  }
};

• 对于越界的情况，合并一下逻辑

class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int n = size(nums1) + size(nums2);
    int x = (n + 1) / 2;
    int y = (n + 2) / 2;
    return (findK(nums1, nums2, 0, 0, x) + findK(nums1, nums2, 0, 0, y)) / 2.0;
  }

  // 查找 nums1 和 nums2 中第 k 小的值
  // a 为 nums1 查找范围的起点，b 为 nums2 查找范围的起点
  double findK(vector<int>& nums1, vector<int>& nums2, int a, int b, int k) {
    if (a >= size(nums1)) {     // nums1 越界
      return nums2[b + k - 1];  // nums2 中从 b 开始第 k 小的数即为结果
    }
    if (b >= size(nums2)) {     // nums2 越界
      return nums1[a + k - 1];  // nums2 中从 b 开始第 k 小的数即为结果
    }
    if (k == 1) {  // k 为 1 则直接取较小的首元素
      return min(nums1[a], nums2[b]);
    }
    int x = a + k / 2 - 1;
    int y = b + k / 2 - 1;
    int m1 = x < size(nums1) ? nums1[x] : INT_MAX;
    int m2 = y < size(nums2) ? nums2[y] : INT_MAX;
    return m1 < m2 ? findK(nums1, nums2, x + 1, b, k - k / 2)
                   : findK(nums1, nums2, a, y + 1, k - k / 2);
  }
};