当前位置: 面试刷题>> 寻找两个正序数组的中位数(经典算法150题)


题目描述

给定两个按非递减顺序排列的正整数数组 nums1nums2,请编写一个函数来找到这两个数组合并后的中位数。

函数应该返回合并后数组的中位数,如果合并后数组长度为奇数,则返回正中间的那个元素;如果合并后数组长度为偶数,则返回中间两个元素的平均值。

注意

  • 你可以假设 nums1nums2 不会同时为空。
  • 两个数组的长度之和不会超过 100。

示例

示例 1:

nums1 = [1, 3]
nums2 = [2]
合并后的数组 = [1, 2, 3]
中位数 = 2

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]
合并后的数组 = [1, 2, 3, 4]
中位数 = (2 + 3) / 2 = 2.5

PHP 代码示例

function findMedianSortedArrays($nums1, $nums2) {
    $merged = array_merge($nums1, $nums2);
    sort($merged);
    $n = count($merged);
    if ($n % 2 == 0) {
        return ($merged[($n / 2) - 1] + $merged[$n / 2]) / 2;
    } else {
        return $merged[floor($n / 2)];
    }
}

// 测试示例
$nums1 = [1, 3];
$nums2 = [2];
echo findMedianSortedArrays($nums1, $nums2);  // 输出 2

$nums1 = [1, 2];
$nums2 = [3, 4];
echo findMedianSortedArrays($nums1, $nums2);  // 输出 2.5

Python 代码示例

def findMedianSortedArrays(nums1, nums2):
    merged = sorted(nums1 + nums2)
    n = len(merged)
    if n % 2 == 0:
        return (merged[n // 2 - 1] + merged[n // 2]) / 2
    else:
        return merged[n // 2]

# 测试示例
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArrays(nums1, nums2))  # 输出 2.0

nums1 = [1, 2]
nums2 = [3, 4]
print(findMedianSortedArrays(nums1, nums2))  # 输出 2.5

JavaScript 代码示例

function findMedianSortedArrays(nums1, nums2) {
    const merged = [...nums1, ...nums2].sort((a, b) => a - b);
    const n = merged.length;
    if (n % 2 === 0) {
        return (merged[Math.floor(n / 2) - 1] + merged[Math.floor(n / 2)]) / 2;
    } else {
        return merged[Math.floor(n / 2)];
    }
}

// 测试示例
const nums1 = [1, 3];
const nums2 = [2];
console.log(findMedianSortedArrays(nums1, nums2));  // 输出 2

const nums1_2 = [1, 2];
const nums2_2 = [3, 4];
console.log(findMedianSortedArrays(nums1_2, nums2_2));  // 输出 2.5

在这些示例中,我们首先合并两个数组,然后对合并后的数组进行排序。根据合并后数组的长度是奇数还是偶数,我们返回相应的中位数。这种方法虽然直观,但在处理大数据集时可能不是最高效的。对于更高效的算法,可以考虑使用二分查找法来避免直接合并和排序整个数组。

推荐面试题