您现在的位置是:首页 > 正文

LeetCode 4. 寻找两个正序数组的中位数(多解法)

2024-04-01 00:52:41阅读 2

解法一:合并数组

将两个数组合并后,直接根据下标找到中位数。时间复杂度 O ( m + n ) O(m + n) O(m+n),空间复杂度 O ( m + n ) O(m + n) O(m+n)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[] mix = new int[n + m];
        // 先执行数组合并
        int i = 0, j = 0, k = 0;
        while (i < n && j < m) {
            if (nums1[i] <= nums2[j]) mix[k++] = nums1[i++];
            else mix[k++] = nums2[j++];
        }
        while (i < n) mix[k++] = nums1[i++];
        while (j < m) mix[k++] = nums2[j++];
        // 合并完毕, 直接找到中位数的下标
        if ((n + m) % 2 == 0) {
            return (mix[(n + m) / 2 - 1] + mix[(n + m) / 2]) / 2.0;
        } else {
            return mix[(n + m) / 2];
        }
    }
}

解法二:双指针

无需合并两个数组,只需要用双指针进行比较并移动到对应位置即可。时间复杂度 O ( m + n ) O(m + n) O(m+n),空间复杂度 O ( 1 ) O(1) O(1)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        // 当 n + m 是偶数时, left, right是中间两个位置
        // 当 n + m 是奇数时, left, right是同一个位置 
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        int cnt = 1; // 当前需要取第几个数
        int median1 = 0, median2 = 0; // 第一个, 第二个位置的数
        int i = 0, j = 0; // 双指针
        while (cnt <= right) {
            int min = 0; // 当前这一轮取到的较小的值
            if (i < n && (j >= m || nums1[i] <= nums2[j])) min = nums1[i++];
            else min = nums2[j++];
            if (cnt == left) median1 = min;
            if (cnt == right) median2 = min;
            cnt++;
        }
        return (median1 + median2) / 2.0;
    }
}

解法三:二分

求两个有序数组的中位数,可以变换为,求第k个数。由于两个数组有序,我们每次只要从两个数组中,分别从左取k/2个数,然后想象尝试将这2组k/2个数合并。若第1组的最后一个数,小于第2组的最后一个数,则第1组不可能作为第k个数,那么可以将第1组的k/2个数全部排除。时间复杂度 O ( l o g ( m + n ) ) O(log(m + n)) O(log(m+n)),空间复杂度 O ( 1 ) O(1) O(1)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        int median1 = getKth(nums1, 0, nums2, 0, left);
        int median2 = getKth(nums1, 0, nums2, 0, right);
        return (median1 + median2) / 2.0;
    }

    // 递归写法
    // 从nums1的下标i开始, 从nums2的下标j开始, 找第k个数
    private int getKth(int[] nums1, int i, int[] nums2, int j, int k) {
        int n = nums1.length, m = nums2.length;
        // 退出条件
        if (i >= n) return nums2[j + k - 1];
        if (j >= m) return nums1[i + k - 1];
        if (k == 1) return Math.min(nums1[i], nums2[j]);
        // 开始二分
        // 从 nums1 中取 k / 2 个数, 并获得其最后一个点, 注意不能越界
        int ie = Math.min(i + k / 2 - 1, n - 1);
        // 从 nums2 中取 k / 2 个数, 并获得其最后一个点
        int je = Math.min(j + k / 2 - 1, m - 1);
        
        if (nums1[ie] <= nums2[je]) {
            // 排除 nums1 的 k / 2个数
            return getKth(nums1, ie + 1, nums2, j, k - (ie - i + 1));
        } else {
            return getKth(nums1, i, nums2, je + 1, k - (je - j + 1));
        }
    }
}

针对getKth方法,再提供一个非递归的写法

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        int median1 = getKth(nums1, nums2, left);
        int median2 = getKth(nums1, nums2, right);
        return (median1 + median2) / 2.0;
    }

    private int getKth(int[] nums1, int[] nums2, int k) {
        int n = nums1.length, m = nums2.length;
        int i = 0, j = 0;
        while (i < n && j < m && k > 1) {
            int ie = Math.min(i + k / 2 - 1, n - 1);
            int je = Math.min(j + k / 2 - 1, m - 1);
            if (nums1[ie] <= nums2[je]) {
                k -= (ie - i + 1); // 更新k
                i = ie + 1; // 更新i, 注意不要先更新i, 再更新 k 
            } else {
                k -= (je - j + 1);
                j = je + 1;
            }
        }

        if (i >= n) return nums2[j + k - 1];
        if (j >= m) return nums1[i + k - 1];
        return Math.min(nums1[i], nums2[j]);
    }
}

解法三:进阶二分(划分数组)

对于数组nums1,其长度为n;数组nums2,其长度为m

对于nums1,我们从中间切开,将其划分为左右两个数组;对于nums2同理。

nums1nums2的左半边数组,合并在一起,称为leftPart;将它们的右半边数组,合并在一起,称为rightPart

只需要保证:

  • len(leftPart) == len(rightPart)(总长度为偶数时),len(leftPart) = len(rightPart) + 1 (总长度为奇数时)
  • max(leftPart) <= min(rightPart)

只需要保证上面的两个条件,则中位数为 (max(leftPart) + min(rightPart)) / 2 (总长度为偶数),或max(leftPart)(总长度为奇数)

接下来我们来看,有多少种划分方式。对于数组nums1,根据其左半边数组的大小,容易得知,共有n + 1种划分方式(即,其左半边数组长度为0,1,2,…,n);对于nums2同理。

我们设i表示某种划分方式下,nums1的左半边数组的大小;设j为某种划分方式下,nums2的左半边数组的大小。

len(leftPart) = i + jlen(rightPart) = n + m - (i + j)

要保证上方的第一个条件。只需要保证 i + j = n + m - (i + j),或 i + j = n + m - (i + j) + 1

变换一下,得 i + j = (n + m + 1) / 2(除法采用向下取整,可兼容长度为偶数和奇数的情况)

由于 max(leftPart) = max(nums1[i], nums2[j]),而min(rightPart) = min(nums1[i + 1], nums2[j + 1])

要保证 max(leftPart) <= min(rightPart),只需要保证 nums1[i] <= nums2[j + 1],并且 nums2[j] <= nums1[i + 1]

由于ij需要满足 i + j = (n + m + 1) / 2,可知ij是呈负相关的。

那么只需要找到,使得 nums1[i] <= nums2[j + 1]成立的最大的i,即可。因为只要i多1,则j必然少1。那么最大的i,满足nums1[i] <= nums2[j + 1],也就蕴含了 nums1[i + 1] >= nums2[j]

所以我们只需要进行二分,找到满足nums1[i] <= nums2[j + 1]的最大的i即可。

对于j的计算,对上面的公式进行变换,得 j = (n + m + 1) / 2 - i,为了使得j不取到负数,当i取最大值n时,

j = (m - n + 1) / 2,我们规定m >= n,即nums2得长度大于等于nums1

由于我们总是对较小的数组进行二分,所以时间复杂度是 O ( l o g ( m i n ( n , m ) ) ) O(log(min(n,m))) O(log(min(n,m))),空间复杂度为 O ( 1 ) O(1) O(1)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        // i + j = (n - i) + (m - j)      总长度为偶数
        // i + j = (n - i) + (m - j) + 1  奇数, 让左侧区间多出一个数
        // i + j = (n + m + 1) / 2        i和j需要满足的关系
        // i = (n + m + 1) / 2 - j        // 需要保证 i >= 0 , 则 n >= m
        if (n < m) return findMedianSortedArrays(nums2, nums1);

        // 开始二分, 对 j 进行二分
        int l = 0, r = m;
        int median1 = 0, median2 = 0;
        while (l <= r) { // 写成 = 确保能二分到最后
            int j = l + r >> 1;
            int i = (n + m + 1) / 2 - j;
            // nums2 左半边的最后一个值 (注意对于j = 0 进行特殊处理)
            int nums2_j = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            // nums2 右半边的第一个值 (注意对 j = m 进行特殊处理)
            int nums2_j_1 = j == m ? Integer.MAX_VALUE : nums2[j];

            int nums1_i = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int nums1_i_1 = i == n ? Integer.MAX_VALUE : nums1[i];

            if (nums2_j <= nums1_i_1) {
                median1 = Math.max(nums2_j, nums1_i);
                median2 = Math.min(nums2_j_1, nums1_i_1);
                l = j + 1; // 往右侧找, 直接跳过当前位置, 确保二分的循环能退出去
            } else {
                r = j - 1; // 往左侧找
            }
        }
        if ((n + m) % 2 == 0) return (median1 + median2) / 2.0;
        else return median1;
    }
}

二分的时候,条件我们写成 l <= r,确保能二分到最后的位置,更新边界时,我们每次都跳过当前位置,即不会更新为l = j这样。确保二分的循环能退出,并且在每次满足条件时,都更新median1median2,记录答案。

网站文章

  • 趣学python算法一百例_DAY1

    趣学python算法一百例_DAY1

    一天应该1道,慢慢做 抓交通肇事犯 1.问题描述 一辆卡车违反交通规则,撞人后逃跑。现场有三人目击该事件,但都没有记住车号,只记下了车号的一些特征。甲说:牌照的前两位数字是相同的;乙说:牌照的后两位数...

    2024-04-01 00:52:14
  • 使用 Git,10个最需要常备的后悔药 热门推荐

    使用 Git,10个最需要常备的后悔药 热门推荐

    Git是目前世界上最优秀最流行的分布式版本控制系统,也是程序员们日常使用最频繁的工具之一(几乎每天都需要使用它来对源代码进行版本管理)。 使用Git的过程,难免由于手快或者别的什么原因,需要对做过的事...

    2024-04-01 00:52:07
  • 基础计算机教研室都上什么课,计算机教研室简介

    计算机教研室现有教授1人、副教授7人、讲师5人,是一支教学实力雄厚、业务素质高、科研能力强,团结友爱的教师团队。截止2021年4月,现有专职教师计算机教研室专职教师(5人): 高谨、翟哲、李宗峰、石沙...

    2024-04-01 00:52:00
  • 本地化部署chatGLM开发实践报错汇总记录

    本地化部署chatGLM开发实践报错汇总记录

    最近因为项目需要在接触chatGLM相关的内容,本地化部署运行是其中之一,在这个学习实践过程中也遇上了很多报错,这里主要是对各种报错的记录汇总,也欢迎大家一起贡献问题与解决方案,希望的就是帮到同样有需要的人。

    2024-04-01 00:51:33
  • 【python脚本】正则匹配提取所需字符串

    python脚本通过正则表达式匹配原文档中所需的字符串,并输出至新的文档中。

    2024-04-01 00:51:23
  • LNK2005: _DllMain@12 already defined解决方案

    LNK2005: _DllMain@12 already defined解决方案

    原因:链接库顺序问题方案:在“项目 -> 属性 -> 链接器 -> 命令行”,使用 /verbose:lib编译参数,输出如下:>SearchingD:\vs2015\VC\lib\MSVCRTD.l...

    2024-04-01 00:51:16
  • JavaScript基础学习——ES6基础指令

    一、认识ES6ES6(ECMAScript 6/ECMAScript 2015)是2015年6月发布的。ES6是对ES5的一个扩展(就是在ES5的基础上添加了一些内容),最典型的内容:Class(类)...

    2024-04-01 00:51:10
  • 证券结算知识

    参考:结算业务 [证券信息技术知识库]目前,我国A股交易实行T+1交收,B股交易实行T+3交收,另外还有部分业务实行逐笔全额交收(Real Time Gross Settlement)、T+0、T+N...

    2024-04-01 00:50:44
  • 单调栈-图解-LeetCode84柱状图中最大的矩形

    单调栈-图解-LeetCode84柱状图中最大的矩形

    概念: 单调栈(monotone-stack)是指栈内元素(栈底到栈顶)都是(严格)单调递增或者单调递减的。 如果有新的元素入栈,栈调整过程中 *会将所有破坏单调性的栈顶元素出栈,并且出栈的元素不会再...

    2024-04-01 00:50:38
  • 应用安全基础

    应用安全基础

    大多数攻击出现在应用层并利用已知漏洞应用安全是一种可供开发人员、测试人员与管理人员在其整个开发过程可用的多层方法论。我们基于计算机的培训课程(CBT)为开发人员、测试人员、项目经理和架构师准备了软件安全开发的最新知识,以培养员工的安全意识,使员工能够设计、创建和部署安全的软件和应用。用户可自行安排时间使用计算机访问课程,同时课程学习环境是高度互动的。课程概述:       本课程描...

    2024-04-01 00:50:30