哈希算法题目：寻找两个有序数组的中位数

题目描述：
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。算法的时间复杂度应该为 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

解题过程循序渐进讲解：

步骤 1：理解中位数的定义与核心难点

• 中位数：将一组数据按大小顺序排列，处在中间位置的一个数（或两个数的平均值）。
• 对于合并后长度为 L 的数组：
  • 若 L 为奇数，中位数是第 (L+1)/2 个数（从1开始计数）。
  • 若 L 为偶数，中位数是第 L/2 个数和第 L/2+1 个数的平均值。
• 直接合并两个数组再找中位数，时间复杂度 O(m+n)，但题目要求 O(log(m+n))，必须用更优方法。
• 关键：不需要真的合并数组，而是“寻找两个有序数组中第 k 小的数”。

步骤 2：转化为寻找第 k 小元素问题

• 设总长度 L = m + n。
• 若 L 为奇数，中位数是第 k = (L+1)/2 小的数。
• 若 L 为偶数，中位数是第 k = L/2 小的数和第 k+1 小的数的平均值。
• 问题转化为：如何在两个有序数组中高效找到第 k 小的数。

步骤 3：二分排除法的思路

• 比较两个数组中第 k/2 个元素（如果存在）：
  • 设 nums1 中第 p1 = min(k/2, m) 个元素为 a。
  • 设 nums2 中第 p2 = min(k/2, n) 个元素为 b。
  • 如果 a ≤ b，那么 nums1 的前 p1 个元素都不可能是第 k 小的数（因为比它们小的最多只有 (p1-1)+(p2-1) ≤ k-2 个）。
  • 因此可以排除 nums1 的前 p1 个元素，将问题转化为在剩余部分中找第 k-p1 小的数。
• 每次排除大约 k/2 个元素，k 不断减小，直到 k=1 或某个数组为空。

步骤 4：递归步骤举例说明
例：nums1 = [1,3,5,7], nums2 = [2,4,6,8,9]，找第 k=5 小的数。

1. k=5, p1=min(2,4)=2, p2=min(2,5)=2。
   a=nums1[1]=3（索引从0开始，第2个元素），b=nums2[1]=4。
   因为 a≤b，排除 nums1 的前2个元素 [1,3]，新 nums1=[5,7]，k 更新为 5-2=3。
2. k=3, p1=min(1,2)=1, p2=min(1,5)=1。
   a=nums1[0]=5, b=nums2[0]=2。
   因为 a>b，排除 nums2 的前1个元素 [2]，新 nums2=[4,6,8,9]，k 更新为 3-1=2。
3. k=2, p1=min(1,2)=1, p2=min(1,4)=1。
   a=nums1[0]=5, b=nums2[0]=4。
   因为 a>b，排除 nums2 的前1个元素 [4]，新 nums2=[6,8,9]，k 更新为 2-1=1。
4. k=1，比较两个数组剩余的第一个元素，nums1[0]=5, nums2[0]=6，取较小者 5。
   所以第5小的数是 5。

步骤 5：处理边界条件

• 如果某个数组长度不足 k/2，则 p 取该数组剩余长度，另一数组正常取 k/2。
• 如果一个数组被全部排除，则直接在另一个数组中取第 k 小的数（即索引 k-1 处）。
• 如果 k=1，直接取两个数组当前首元素的较小值。

步骤 6：算法实现伪代码

function findKth(nums1, start1, nums2, start2, k):
    // 如果 nums1 已全部排除
    if start1 >= len(nums1):
        return nums2[start2 + k - 1]
    // 如果 nums2 已全部排除
    if start2 >= len(nums2):
        return nums1[start1 + k - 1]
    // 如果 k=1
    if k == 1:
        return min(nums1[start1], nums2[start2])
    
    // 计算比较位置
    p1 = min(len(nums1) - start1, k // 2)
    p2 = min(len(nums2) - start2, k // 2)
    
    if nums1[start1 + p1 - 1] <= nums2[start2 + p2 - 1]:
        // 排除 nums1 的前 p1 个元素
        return findKth(nums1, start1 + p1, nums2, start2, k - p1)
    else:
        // 排除 nums2 的前 p2 个元素
        return findKth(nums1, start1, nums2, start2 + p2, k - p2)

步骤 7：求中位数的完整逻辑

L = m + n
if L 是奇数:
    return findKth(nums1, 0, nums2, 0, (L+1)//2)
else:
    left  = findKth(nums1, 0, nums2, 0, L//2)
    right = findKth(nums1, 0, nums2, 0, L//2 + 1)
    return (left + right) / 2

步骤 8：复杂度分析

• 每次递归 k 减少约一半，k 最大为 (m+n)/2，因此递归深度为 O(log(m+n))。
• 每次递归操作是常数时间，总时间复杂度 O(log(m+n))，满足要求。
• 空间复杂度 O(log(m+n))（递归栈），可优化为迭代实现达到 O(1)。

关键点总结：

1. 将中位数问题转化为两个有序数组中第 k 小的数问题。
2. 通过比较两个数组的第 k/2 个元素，每次排除不可能的部分，不断缩小 k。
3. 递归处理，注意数组越界和 k=1 的边界条件。
4. 根据总长度奇偶性，调用一次或两次 findKth 得到中位数。