Médiane de deux rangées triées de tailles différentes

Question

J'essaie de trouver la médiane de deux rangées triées de tailles différentes. Mais il y a quelques situations où cela ne fonctionne pas et je n'ai pas pu comprendre pourquoi. J'ai inclus ma mise en œuvre ci-dessous. Je suis conscient qu'il existe des solutions similaires en ligne. Mais je commence juste à apprendre des algorithmes et je veux en faire autant que possible par moi-même. Merci beaucoup d'avance pour votre aide!

public double median(Point[] arr, int start, int end) { 
    int n = end - start + 1; 
    if (n % 2 == 0) { 
     return (double) (arr[start + (n/2)].getSz() + arr[start + (n/2) - 1].getSz())/2; 
    } 
    else { 
     return (double) arr[start + (n/2)].getSz(); 
    } 
} 

public double getMedian(int aStart, int aEnd, int bStart, int bEnd) { 
    int m = aEnd - aStart + 1; 
    int n = bEnd - bStart + 1; 
    double median = 0; 

    if (m == 0 && n > 0) { 
     return median(arr2, 0, bEnd); 
    } 

    if (m > 0 && n == 0) { 
     return median(arr1, 0, aEnd); 
    } 

    if (m == 1 && n == 1) { 
     return (double) (arr1[0].getSz() + arr2[0].getSz())/2; 
    } 

    if (m == 2 && n == 2) { 
     median = (double) (Math.max(arr1[aStart].getSz(), arr2[bStart].getSz()) + Math.min(arr1[aEnd].getSz(), arr2[bEnd].getSz()))/2; 
     return median; 
    } 

    double m1 = median(arr1, aStart, aEnd); 
    double m2 = median(arr2, bStart, bEnd); 

    if (m1 == m2) { 
     return m1; 
    } 

    if (m1 < m2) { 
     if (m % 2 == 0) { 
      aStart = aStart + (m/2) - 1; 
      index = 1; 
     } 
     else { 
      index = 2; 
      aStart = aStart + m/2; 
     } 
     bEnd = bStart + n/2; 
    } 
    else { 
     if (n % 2 == 0) { 
      index = 3; 
      bStart = bStart + n/2 - 1; 
     } 
     else { 
      index = 4; 
      bStart = bStart + n/2; 
     } 
     aEnd = aStart + m/2; 
    } 
    return (getMedian(aStart, aEnd, bStart, bEnd)); 
} 

Voici un exemple pour lequel les pauses logiques:
arr1 = 6, 20, 28, 29, 36, 41
arr2 = 14, 25, 33, 47, 53, 66, 79, 98

correcte médiane = 34,5
médiane estimée = 31

Answer 1

On dirait qu'il ya quelques problèmes dans l'algorithme.

Tout d'abord 0 est utilisé au lieu de aDEBUT et bDEBUT dans deux endroits:

if (m == 0 && n > 0) { 
     return median(arr2, ->0<-, bEnd); 
    } 

    if (m > 0 && n == 0) { 
     return median(arr1, ->0<-, aEnd); 
    } 

    if (m == 1 && n == 1) { 
     return (double) (arr1[->0<-].getSz() + arr2[->0<-].getSz())/2; 
    } 

En second lieu; Dans le dernier bloc, vous devez faire attention à ne pas jeter autant de valeurs au-dessus de la médiane que sous celle-ci.

if (m1 < m2) { 
    if (m % 2 == 0) { 
     aStart = aStart + (->m<-/2) - 1; 
     index = 1; 
    } 
    else { 
     index = 2; 
     aStart = aStart + ->m<-/2; 
    } 
    bEnd = bStart + ->n<- /2; 
} 

et aussi de ne pas jeter les valeurs les plus proches de la médiane où la médiane est calculée sur un nombre pair de données. J'espère que cela pourra aider.

Answer 2

Pour obtenir la médiane des deux tableaux triés A et B, vous devez savoir comment diviser les deux tableaux dans une partie basse et une partie haute, de sorte que tous les éléments de faible partie sont < = all les éléments de la partie haute, et le nombre total d'éléments dans les parties basse et haute sont les mêmes (à moins de 1).

Les éléments faibles seront constitués d'un certain nombre x d'éléments de A, et (a.length + B.length)/2 - x éléments de B.

Pour trouver x, vous effectuez une recherche binaire sur les valeurs possibles de x. Soit MID = (A.length + B.length)/2. Ensuite, en supposant x, si A [x-1]> B [MID-x] alors x est trop grand. Sinon ce n'est pas trop gros. Cette condition est suffisante pour vous permettre de réduire la plage de valeurs de moitié à chaque itération.

Une fois que vous où les réseaux sont divisés, vous que max (A [x-1], B [MID-x-1]) est l'élément le plus élevé dans les parties basses, et min (A [x], B [MID-x]) est l'élément le plus bas dans les parties hautes, et c'est tout ce dont vous avez besoin pour calculer la médiane.