首页 > 其他分享 >【LeetCode Hot 100】4. 寻找两个正序数组的中位数

【LeetCode Hot 100】4. 寻找两个正序数组的中位数

时间:2024-09-19 15:03:37浏览次数:10  
标签:正序 int 元素 中位数 Hot 数组 100 nums1 nums2

题目描述

要求出两个数组的中位数,第一想法当然是将这两个数组进行归并排序,然后直接得到排序后长数组的中位数。由于本题的两个数组都是排序后的数组,因此省去了排序的步骤。这种方法的时间复杂度为\(O(m+n)\),空间复杂度由于要存储排序后的长数组,所以也是\(O(m+n)\)。

有没有相对更简单的方法呢?由于我们只需要求出中位数,并不需要得到合并后的数组,所以我们可以从左往右逐个元素遍历并计数,只要我们达到了中位数所需要的下标,就可以停下来并计算中位数了。需要注意的是,如果总长度为奇数,中位数应该是中间两个元素的算术平均,因此除了当前元素之外,还需要维护前一个元素。显然,这种方法的时间复杂度为\(O(\frac{m+n}{2})\),空间复杂度则相对第一种方法优化为了常数级。

// C++
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int len = m + n;
        int prev = -1, curr = -1;
        int i = 0, j = 0;
        for (int cnt = 0; cnt <= len / 2; cnt++) {
            prev = curr;
            if (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    curr = nums1[i++];
                } else {
                    curr = nums2[j++];
                }
                continue;
            }
            if (i < m) {
                curr = nums1[i++];
            }
            if (j < n) {
                curr = nums2[j++];
            }
        }
        if (len % 2) {
            return curr;
        }
        return (prev + curr) / 2.0;
    }
};

但是,题目描述中要求解法的时间复杂度为对数级别,看到这个要求,就要想到与二分有关。

要找到两个数组的中位数,就是要找到第\(\frac{m+n}{2}\)小(和第\(\frac{m+n}{2}+1\)小)的元素。这个方法则给出了更通用的方法,用于求出第\(k\)小的元素。

要找到两个升序数组总共的第\(k\)小的元素,我们可以先比较两个数组下标为k/2 - 1的元素,假设a[k/2 - 1] < b[k/2 - 1],那么a数组的前面几个元素只会更小,我们即使假设b数组的前面几个元素都比a[k/2 - 1]小,此时该元素也“仅仅”是总共第\(\frac{k}{2}-1\)小的元素,也就是说它最大也只能达到这个程度,而绝不可能是第\(k\)小的元素,那么我们就可以放心地把a[0..k/2-1]这个子数组全部“丢弃”不看,这样我们一次性排除了\(\frac{k}{2}\)个元素。随后我们可以继续用这个方法排除下去,直到k=1

当然,有一些特殊情况需要考虑:

  • a[k/2 - 1]b[k/2 - 1]越界,我们需要选取的是数组的最后一个元素。
  • 其中一个数组的元素全部被排除,可以直接返回另一个数组第\(k\)小的元素。
  • \(k=1\),只要返回第一个元素的较小值即可。
// C++
// https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/258842/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
class Solution {
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        /* 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数
         */

        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1) {
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        }
        else {
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
};

标签:正序,int,元素,中位数,Hot,数组,100,nums1,nums2
From: https://www.cnblogs.com/louistang0524/p/18420549

相关文章

  • Hi3559A/C V100 集成了双核 A73 和双核 A53,支持 8K30/4K120 视频录制
    1.1概述Hi3559AV100是专业的8KUltraHDMobileCameraSOC,它提供了8K30/4K120广播级图像质量的数字视频录制,支持多路Sensor输入,支持H.265编码输出或影视级的RAW数据输出,并集成高性能ISP处理,同时采用先进低功耗工艺和低功耗架构设计......
  • TP5100 2A开关降压 8.4V/4.2V锂电池充电器芯片
    1概述●TP5100是一款开关降压型双节8.4V/单节4.2V锂电池充电管理芯片。其QFN16超小型封装与简单的外围电路,使得TP5100非常适用于便携式设备的大电流充电管理应用。同时,TP5100内置输入过流、欠压保护、芯片过温保护、短路保护、电池温度监控。●TP5100具有5V-12V输入电压......
  • 【Java计算机毕设选题】2025毕业设计选题100+ 通过率最高的选题推荐
    文章目录前言选题介绍选题推荐我的优势源码获取前言❤️博主简介:全网累计客户1000+,培训机构讲师、全栈开发工程师、知乎/小红书优秀作者、腾讯云/阿里云VIP客户、专注Java、小程序、安卓领域和毕业项目开发❤️同学们可以先收藏起来,以免迷路,关于毕设选题,项目和论文的......
  • 视频监控平台AS-V1000的场景管理,如何切换不同场景的多画面视频,快速浏览自己需要的实时
    目录一、需求二、分析1.视频管理系统(iVMS)2.地图视图3.多画面分割4.建立多场景管理三、实现方式1、系统介绍(1)AS-V1000介绍(2)平台服务器配置说明2、场景管理(1)如何使用场景管理页面(2)保存场景管理(3)场景列表3、应用效果(1)调用四画面效果(2)调用九画面效果一......
  • VastbaseG100集群部署实操
    背景近日的工作涉及到数据库的集群部署,为了熟悉过程,参考VastgbaseG100官方文档进行部署。参考文档https://docs.vastdata.com.cn/zh/docs/VastbaseG100Ver2.2.15/do...实操这里采用HAS+DCS+Vastbase的解决方案,详情可参考海量智库第8期|VastbaseG100核心技术介绍之高可用软件......
  • 《怪物猎人物语:复刻版》游戏启动时闪退弹窗“找不到vcomp100.dll”该怎么办?怪物猎人物
    当启动《怪物猎人物语:复刻版》时,游戏闪退并弹窗显示“找不到vcomp100.dll”,这可让人着急。或许需要对系统进行修复、更新相关程序,或者重新获取该文件。您遇到过这种情况吗?知道该如何应对吗?本篇将为大家带来《怪物猎人物语:复刻版》游戏启动时闪退弹窗“找不到vcomp100.dll”该怎......
  • Align Your Prompts论文解读: Test-Time Prompting with Distribution Alignment for
    Comment:AcceptedtoNeurIPS2023对齐提示:用于zero-shot泛化的测试时提示分布对齐摘要CLIP等视觉语言模型的zero-shot泛化已经引领它们在下游任务中使用提示学习。先前的工作已经表明使用熵最小化进行测试时提示调优,调整文本提示适应未见过的领域。尽管这样的方法非常高效......
  • 【计算机毕设选题】2025计算机毕业设计选题,毕设100个热门选题推荐
    毕业设计作为计算机专业学生学习阶段的压轴之作,不仅是展示知识与技能的机会,更是对实际开发能力的全面考验。选题是整个毕业设计过程中至关重要的一环,一个合适且有挑战性的题目能大大提升毕业设计的质量。然而,很多学生在选题时面临着两个难题:一是题目过于常规,无法充分展现个......
  • 【数据结构与算法 | 灵神题单 | 自底向上DFS篇】力扣965, 2331, 100, 1379
    1.力扣965:单值二叉树1.1题目:如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回 true;否则返回 false。示例1:输入:[1,1,1,1,1,null,1]输出:true示例2:输入:[2,2,2,5,2]输出:false提示:给定树的节点数范围是 [1,......
  • CPU探针和监控指标事项(不少于100种)
    在机器监控中,CPU的监控指标确实非常多样化。以下是20多种重要的CPU指标及其作用:CPU使用率(CPUUtilization)作用:反映CPU整体负载情况,通常以百分比表示。用户时间(UserTime)作用:显示CPU在用户模式下执行程序的时间比例。系统时间(SystemTime)作用:表示CPU在内核模式下执......