Mediana z 2 posortowanych tablic o różnych długościach

Question

Jak można znaleźć medianę 2 posortowanych tablic A i B o długości odpowiednio m i n. Mam wyszukiwane, ale większość algorytmów zakłada, że ​​obie tablice są tej samej wielkości. Chcę wiedzieć, jak znaleźć medianę, jeśli m! = N rozważmy przykład, A = {1, 3, 5, 7, 11, 15} gdzie m = 6, B = {2, 4, 8, 12 , 14} gdzie n = 5 , a mediana to 7

Każda pomoc jest doceniana. Przygotowuję się do wywiadów i walczę teraz z tym algo.

Answer 1

Wyszukiwanie liniowe dla elementu medianowego jest równe O (m + n) ze stałą powierzchnią. Nie jest to optymalne, ale realistyczne jest przedstawienie w wywiadzie.

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 2

Oto kod Java, aby znaleźć medianę dwóch posortowanych tablic o nierównej długości

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 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; 
     } 
    }