विभिन्न लंबाई के 2 क्रमबद्ध सरणी के औसत

Question

कैसे क्रमशः 2 क्रमबद्ध एरे और ए क्रमशः एम और एन के मध्यस्थ को प्राप्त कर सकते हैं। मैंने खोज की है, लेकिन अधिकांश एल्गोरिदम मानते हैं कि दोनों सरणी एक ही आकार के हैं। मैं जानना चाहता हूं कि हम मध्यस्थ कैसे मिल सकते हैं यदि एम! = एन उदाहरण पर विचार करें, ए = {1, 3, 5, 7, 11, 15} जहां एम = 6, बी = {2, 4, 8, 12 , 14} जहां एन = 5 और औसत 7

किसी भी मदद की सराहना की जाती है। मैं साक्षात्कार के लिए तैयारी कर रहा हूं और मैं अभी इस अहंकार से जूझ रहा हूं।

Answer 1

मध्यस्थ आदेश के लिए एक रैखिक खोज निरंतर स्थान के साथ ओ (एम + एन) होगी। यह इष्टतम नहीं है, लेकिन एक साक्षात्कार में उत्पादन करना यथार्थवादी है।

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

यहाँ

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