如何以O(log(m+n))时间复杂度寻找两个有序数组的中位数

实现思路 #

• 先获取两个输入有序数组的长度，计算合并后数组的总长度
• 创建一个总长度的新数组，将两个输入数组的元素分别拷贝到新数组的对应位置
• 对合并后的数组进行排序
• 根据数组长度的奇偶性计算中位数：
  • 长度为奇数时，中位数是数组中间索引位置的元素
  • 长度为偶数时，中位数是中间两个元素的平均值

Java 实现代码 #

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      
        int[] a = nums1;
        int[] b = nums2;

        int c = a.length + b.length;

        int[] myArr = new int[c];

        for (int i = 0; i < a.length; i++) {
            myArr[i] = a[i]; 
        }

        for (int i = 0; i < b.length; i++) {
            myArr[a.length + i] = b[i]; 
        }

        Arrays.sort(myArr);

        double median;
        int lastIndex = myArr.length - 1;

        int middle = lastIndex / 2;

        if (myArr.length % 2 != 0) {
            median = myArr[middle];
        } else {
            median = (myArr[middle] + myArr[middle + 1]) / 2.0;
        }

        return median;

    }
}

内容的提问来源于stack exchange，提问作者Fazeel Ayaz