IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 4.寻找两个正序数组的中位数 -> 正文阅读

[数据结构与算法]4.寻找两个正序数组的中位数

作者 : XiaXinyu
日期 :2021-09-21

题目

理解

给定两个升序的数组,找出由这两个数组合并后的升序数组中的中位数

题解1(朴素做法——双指针合并数组)

这道题首先我想到的最直观的做法就是利用双指针将两个数组合并成一个有序数组

合并之后在新数组中找出中位数即可

这种做法应该是最容易理解的

伪代码

  • 初始化新数组,长度为给定两个数组的长度之和

  • 初始化指向两个数组的指针i,j以及新数组指针cnt

  • 当 i 小于 nums1的长度时或 j 小于nums2的长度时执行循环

    • 当 i 小于 nums1的长度时,val1等于nums1[i],否则等于int型整数最大值
    • 当 j 小于 nums2的长度时,val2等于nums2[j],否则等于int型整数最大值
    • 如果val1 小于等于 val2则新数组中填入val1指针i 后移
    • 否则新数组中填入val2指针j 后移
    • (注 : 这里让val1 和val2 取整数最大值是由于当 i 或 j >= 所指向数组长度时,那么新数组中只能填入 j 或 i 所指向的值)
  • 判断新数组长度是否为奇数

    • 若为奇数直接返回中间值即可
    • 若为偶数返回中间两个值的平均数即可

代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] a = new int[nums1.length + nums2.length];
        int i = 0,j = 0;
        int cnt = 0;
        while(i < nums1.length || j < nums2.length){
            {
                int val1 = i < nums1.length ? nums1[i] : Integer.MAX_VALUE;
                int val2 = j < nums2.length ? nums2[j] : Integer.MAX_VALUE;
                if(val1 <= val2){
                        a[cnt ++] = val1;
                        i ++;
                    }
                else{
                        a[cnt ++] = val2;
                        j ++;
                    }
            }
        
        }
        if(a.length % 2 != 0) return a[a.length / 2];
        
        return 1.0 * (a[a.length / 2] + a[a.length / 2 - 1]) / 2;
    }
}

时间复杂度 :O(n + m) 使用双指针算法,会将两个数组都遍历一遍,n为数组1的长度,m为数组2的长度

空间复杂度 :O(n + m) 开辟新数组的空间为n + m

题解二

题解二的思路来源于这里

在题解一中我们遍历了两个数组的所有元素,其实并不需要这样做,只需要遍历到可确定中位数的元素即可

先讨论一下奇偶性的情况,假设两个数组的总长度为len

当len为奇数时,中位数的位置在len / 2 + 1,

当len为偶数时,中位数为在len / 2 和 len / 2 + 1的两个数的平均值

所以无论len为奇数还是偶数,只需遍历到 len / 2 + 1 个元素即可,将两个数组分别称为A,B

首先初始化astart和bstart分别作为指向A,B数组的指针,left为上一次遍历到的元素值,right为当前遍历的元素值

当astart小于数组A的长度时并且bsatrt > B数组长度或 A[astart] < B[bstart]这两个条件中有一个成立一个令astart右移,否则bstart右移,right的值更新为astart或bstart指针右移之前所指向的值

注意在每次循环时都要让left的值等于right,这样处理后,在遍历结束时,right的值为遍历到最后一个元素的值,left值为最后遍历到最后一个元素的前一个元素的值

class Solution{
    public double findMedianSortedArrays(int[] a, int[] b){
        int right = -1,left = -1;
        int astart = 0,bstart = 0;
        int len = a.length + b.length;
        for(int i = 0;i <= len / 2;i ++){
            left = right;
            if(astart < a.length && (bstart >= b.length || a[astart] < b[bstart]))
            right = a[astart ++];
            else
            right = b[bstart ++];

        }
        if((len & 1) == 0) return (right + left) / 2.0;
        else return right;
    }
    
}

时间复杂度 :O(m + n) 虽然我们遍历了len / 2 + 1次, 但是len = (m + n) / 2,所以时间复杂度仍然为O(m + n)

空间复杂的 :O(1)

题解3(二分法)

待完善

  数据结构与算法 最新文章
索引知识点
九章算法班2021版「完结无密」
39. 组合总和
【LeetCode 深度优先搜索专项】不同岛屿的数
动态规划思维导图
强化学习第3章——动态规划
LeetCode 每日一题 2021/8/16-2021/8/22
完全二叉树的节点数
leetcode42. 接雨水
公园遛狗 / 小白逛公园【ybt高效进阶4-4-3】
上一篇文章      下一篇文章      查看所有文章
加:2021-09-26 10:26:26  更:2021-09-26 10:28:55 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年10日历 -2021/10/28 12:48:58-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码