LeetCode刷题 题4. 寻找两个正序数组的中位数
发布日期:2021-05-20 10:42:27 浏览次数:21 分类:精选文章

本文共 1123 字,大约阅读时间需要 3 分钟。

首先,理解什么是中位数。在整理好数据后,找到中间的数或平均数。两个数组已排序,便于合并或对比。

合并两个已排序的数组可以选择低内存的方法,用指针逐个比较。同时,考虑测试边界情况如空数组。

以下步骤简明明了地解释了如何计算中位数:

方法思路:

  • 初始化指针和结果数组。
  • 逐个比较数,直到合并完毕。
  • 处理剩余元素并确定中位数。
  • 在代码中处理特殊情况,确保正确计算。
  • -sort-array-example

    如示例,合并后的数组为[1,2,3,4],中位数为2.5。

    最终代码:

    double findMedianSortedArrays(vector
    & nums1, vector
    & nums2) {
    vector
    merged;
    int i = 0, j = 0;
    int n = nums1.size();
    int m = nums2.size();
    while (i < n && j < m) {
    if (nums1[i] <= nums2[j]) {
    merged.push_back(nums1[i]);
    i++;
    } else {
    merged.push_back(nums2[j]);
    j++;
    }
    }
    while (i < n) {
    merged.push_back(nums1[i]);
    i++;
    }
    while (j < m) {
    merged.push_back(nums2[j]);
    j++;
    }
    if (n + m == 1) {
    return (double)merged[0];
    } else if ((n + m) % 2) {
    return (double)merged[(n + m - 1)/2];
    } else {
    return (double)(merged[n + m / 2 - 1] + merged[n + m / 2]) / 2;
    }
    }

    请注意这一实现假设输入数组的类型已经被正确声明。测试时确保输入数据合法。

    合并两个有序数组的指针方法节省了内存,避免了额外的排序开销。确保代码中的条件判断正确处理了所有情况。

    上一篇:LeetCode刷题 题5. 最长回文子串
    下一篇:计算机网络笔记

    发表评论

    最新留言

    网站不错 人气很旺了 加油
    [***.192.178.218]2025年05月07日 19时15分35秒