[数据结构与算法]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(二分法)

待完善