arrays - 2个不同长度的排序数组的中位数

Question

如何找到长度分别为 m 和 n 的 2 个排序数组 A 和 B 的中位数。我已经搜索过了，但大多数算法都假设两个数组的大小相同。我想知道如果 m != n 考虑例如 A={1, 3, 5, 7, 11, 15} 其中 m = 6, B={2, 4, 8, 12, 14}，我们如何找到中位数其中 n = 5，中位数为 7

任何帮助表示赞赏。我正在准备面试，我现在正在努力解决这个问题。

Answer 1

这是查找两个长度不等的排序数组的中位数的JAVA代码

package FindMedianBetween2SortedArraysOfUnequalLength;

import java.util.Arrays;
import java.util.Scanner;

public class UsingKthSmallestElementLogic {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    try{
        System.out.println("Enter the number of elements in the first SORTED array");
        int n = in.nextInt();
        int[] array1 = new int[n];
        System.out.println("Enter the elements of the first SORTED array");
        for(int i=0;i<n;i++)
            array1[i]=in.nextInt();
        System.out.println("Enter the number of elements in the second SORTED array");
        int m = in.nextInt();
        int[] array2 = new int[m];
        System.out.println("Enter the elements of the second SORTED array");
        for(int i=0;i<m;i++)
            array2[i]=in.nextInt();
        System.out.println("Median of the two SORTED arrays is: "+findMedian(array1,array2,array1.length,array2.length));
    }
    finally{
        in.close();
    }
}
private static int findMedian(int[] a, int[] b,
        int aLength, int bLength) { 

    int left = (aLength+bLength+1)>>1;
    int right = (aLength+bLength+2)>>1;
    return ((findKthSmallestElement(a,b,a.length,b.length,left)+findKthSmallestElement(a,b,a.length,b.length,right))/2);
}
private static int findKthSmallestElement(int[] a, int[] b,
        int aLength, int bLength, int k) {                    // All the 5 parameters passed are VERY VERY IMP

    /* to maintain uniformity, we will assume that size_a is smaller than size_b
    else we will swap array in call :) */
    if(aLength>bLength)
        return findKthSmallestElement(b, a, bLength, aLength, k);

    /* We have TWO BASE CASES
     * Now case when size of smaller array is 0 i.e there is no elemt in one array*/
    //BASE CASE 1. If the smallest array length is 0
    if(aLength == 0 && bLength > 0)
            return b[k-1]; // due to zero based index

    /* case where k==1 that means we have hit limit */
    //BASE CASE 2. If k==1
    if(k==1)
            return Math.min(a[0], b[0]);

    /* Now the divide and conquer part */
    int i =  Math.min(aLength, k/2) ; // k should be less than the size of array  
    int j =  Math.min(bLength, k/2) ; // k should be less than the size of array  

    if(a[i-1] > b[j-1])
            // Now we need to find only K-j th element
            return findKthSmallestElement(a, Arrays.copyOfRange(b, j, b.length), a.length, b.length -j, k-j);
    else
            return findKthSmallestElement(Arrays.copyOfRange(a, i, a.length), b, a.length-i, b.length,  k-i);
}
}
/*
Analysis:
    Time Complexity = O(log(n+m))
    Space Complexity = O(1)*/

Answer 2

对中位数有序元素的线性搜索将是 O(m + n) 且具有恒定空间。这不是最佳的，但在采访中产生是现实的。

numElements = arr1.length + arr2.length
elementsToInspect = floor(numElements / 2)
i1 = 0
i2 = 0

if elementsToInspect == 0
    return arr1[i1]

while (1) {
    if (arr1[i1] < arr2[i2]) {
        i1++
        elementsToInspect--
        if elementsToInspect == 0
            return arr1[i1]
    } else {
        i2++
        elementsToInspect--
        if elementsToInspect == 0
            return arr2[i2]
    }
}

Answer 3

A simple O(log(m + n)) solution: watch video https://www.youtube.com/watch?v=LPFhl65R7ww   

 class Solution {
        public double findMedianSortedArrays(int[] arr1, int[] arr2) {
                    if(arr1 == null && arr2 == null) {
                return -1;
            }
            if(arr1.length == 0 && arr2.length == 0) {
                return -1;
            }

            int x = arr1.length;
            int y = arr2.length;

            if(x > y) {
                return findMedianSortedArrays(arr2, arr1);
            }
            int low = 0;
            int high = x;
            while (low <= high) {
                int partitionX = (low + high) / 2;
                int partitionY = (x + y + 1) / 2 - partitionX;

                int maxX = partitionX == 0 ? Integer.MIN_VALUE : arr1[partitionX - 1];
                int minX = partitionX == x ? Integer.MAX_VALUE : arr1[partitionX];

                int maxY = partitionY == 0 ? Integer.MIN_VALUE : arr2[partitionY - 1];
                int minY = partitionY == y ? Integer.MAX_VALUE : arr2[partitionY];

                if(maxX <= minY && maxY <= minX) {
                    if((x + y)%2 == 0) {
                        return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
                    } else {
                        return Math.max(maxX, maxY);
                    }
                } else if(maxX > minY) {
                    high = partitionX - 1;
                } else {
                    low = partitionX +  1;
                }
            }
            return  -1;
        }
    }