2011 408 真题解答

🧑‍💻 作者: 一可爱小白兔

📦 版本: 1.0.0

📄 字数(字): 0

⏳ 时长(min): 0

⏱️ 更新于: 2026-01-08

问题描述

一个长度为 L(L>=1)的升序序列 S，处在第 L/2(向下取整)个位置的数称为 S 的中位数。如序列 s1={ 11，13，15，17，19} 中位数为 15。
而两个升序序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2={2,4,6,8,20},则 s1 和 s2 的中位数是 11。
现有两个等长的升序序列 A 和 B，设计一个在时间和空间两方面尽可能高效的算法，找出序列 A 和 B 的中位数。

算法设计思想

模拟归并过程，计数至第 n 个元素

• 使用两个指针 i 和 j 分别遍历 nums_1 和 nums_2。
• 每次将较小的元素“取出”（但不真正合并），并移动对应指针。
• 记录当前取出的元素为 mid。
• 当总共取出了 n 个元素时（即 i + j == n），停止循环，返回最后一个取出的元素

代码实现

int findMid(vector<int> &nums_1, vector<int> &nums_2) {
    int n = nums_1.size();
    int i = 0, j = 0;
    int midNum = 0;
    while (i < n && j < n) {
        if (nums_1[i] < nums_2[j]) {               // nums_1[i] < nums_2[j]时,"取数",移动nums_1的指针i
            midNum = nums_1[i];
            i++;
        } else {
            midNum = nums_2[j];                   // nums_1[i] >= nums_2[j]时,"取数",移动nums_2的指针j
            j++;
        }
        if (i + j == n)                           // 当取出 n 次时, 退出
            break;
    }
    return midNum;
}

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(1)

更优解法

不断比较并舍弃两序列中不可能包含中位数的部分

• 循环二分: while (s_1 < d_1 || s_2 < d_2)
  • 计算中位数的索引: m_1 = s_1 + (d_1 - s_1) / 2; m_2 = s_2 + (d_2 - s_2) / 2;
  • 比较 nums_1[m_1] 和 nums_2[m_2]:
  • 如果 nums_1[m_1] == nums_2[m_2]，则返回中位数。
  • 如果 nums_1[m_1] < nums_2[m_2]，中位数一定不在 nums_1 的前半部分(s_1~m_1)，也不在 nums_2 的后半部分 (m_2~d_2);
    ❤️ 判断淘汰的边界:
    如果剩余元素数是奇数，淘汰 nums_1 的 s_1 ~ m_1 包含 m_1, 否则淘汰 nums_1 的 s_1 ~ m_1 不包含 m_1;
    淘汰 nums_2 的 m_2(不包含) ~ d2
  • 否则，调整策略相反
• 循环结束: 当两个序列都剩一个元素时，比较两个序列的元素，返回较小的元素。

int findMid(vector<int> &nums_1, vector<int> &nums_2) {
    int s_1 = 0, d_1 = nums_1.size() - 1;
    int s_2 = 0, d_2 = nums_2.size() - 1;
    while (s_1 < d_1 || s_2 < d_2) {
        int m_1 = s_1 + (d_1 - s_1) / 2;
        int m_2 = s_2 + (d_2 - s_2) / 2;
        if (nums_1[m_1] == nums_2[m_2])                        // 如果 nums_1[m_1] < nums_2[m_2],则返回中位数
            return nums_1[m_1];
        if (nums_1[m_1] < nums_2[m_2]) {                       // 如果 nums_1[m_1] < nums_2[m_2]
            s_1 = (d_1 - s_1 + 1) % 2 == 0 ? m_1 + 1 : m_1;    // 淘汰 nums_1[m_1]左边的部分(关键: 奇数个淘汰包含 m_1)
            d_2 = m_2;                                         // 淘汰 nums_2[m_2]右边的部分
        } else {
            s_2 = (d_2 - s_2 + 1) % 2 == 0 ? m_2 + 1 : m_2;
            d_1 = m_1;
        }
    }
    return min(nums_1[s_1], nums_2[s_2]);                      // 此时, s_1, s_2 各剩下一个元素，取最小
}

• 时间复杂度: O(log n)
• 空间复杂度: O(1)