如何以 O(log(m+n)) 复杂度找到两个排序数组的中位数

Question

我复制两个初始数组的长度，然后将它们合并为第三个数组，第三个数组的长度等于初始两个数组的长度相加。然后我尝试找到合并数组的中位数。

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;

    }
}

Answer 1

使用两个指针（这里的想法）：

public double findMedianSortedArrays(int[] arr1, int[] arr2) {
    int i = 0, j = 0;
    int size1 = arr1.length;
    int size2 = arr2.length;
    List<Integer> result = new ArrayList<>();

    while (i < size1 && j < size2) {
        if (arr1[i] < arr2[j]) {
            result.add(arr1[i++]);
        } else {
            result.add(arr2[j++]);
        }
    }

    while (i < size1) {
        result.add(arr1[i++]);
    }
    while (j < size2) {
        result.add(arr2[j++]);
    }

    int mid = result.size() / 2;
    if (result.size() % 2 == 0) {
        return (result.get(mid - 1) + result.get(mid)) / 2.0;
    }
    return result.get(mid);
}