Comment calculer la médiane d'un tableau?

trier le tableau est inutile et inefficace. Il y a une variante de L'algorithme de QuickSort ( QuickSelect ) qui a un temps d'exécution moyen de O(n); Si vous triez en premier, vous êtes à O(N log n). Il trouve en fait le nième plus petit élément dans une liste; pour une médiane, vous n'utilisez que n = la moitié de la longueur de la liste. Appelons-le quickNth (list, n).

le concept est que pour trouver le nième plus petit, choisir une valeur de "pivot". (Exactement comment vous choisissez ce n'est pas critique; si vous savez que les données seront complètement aléatoires, vous pouvez prendre le premier élément sur la liste.)

divise la liste originale en trois listes plus petites:

• une avec des valeurs plus petites que le pivot.
• un avec des valeurs égales au pivot.
• et dont les valeurs sont supérieures au pivot.

vous avez alors trois cas:

1. la "plus petite" liste A >= n articles. Dans ce cas, vous savez que le nième plus petit est dans cette liste. Retourner quickNth (plus petit, n).
2. la liste plus petite A < N articles, mais la somme des longueurs des listes plus petites et égales ont >= N articles. Dans ce cas, le nth est égal à n'importe quel article de la liste "égal"; vous êtes fait.
3. n est supérieur à la somme des longueurs des listes plus petites et égales. Dans ce cas, vous pouvez essentiellement sauter sur ces deux-là, et ajuster n en conséquence. Retourner quickNth(plus grand, n - Longueur(plus petit) - longueur (égal)).

fait.

Si vous n'êtes pas sûr que les données sont complètement aléatoires, vous devez être plus sophistiqué sur le choix du pivot. Prendre la médiane de la première valeur dans la liste, la dernière valeur dans la liste, et le milieu entre les deux fonctionne assez bien.

Si vous êtes très malchanceux avec votre choix de pivots, et vous choisissez toujours la plus petite ou la plus haute valeur comme votre pivot, cela prend O(N^2) temps; c'est mauvais. Mais, c'est aussi très peu probable si vous choisissez votre pivot avec un algorithme décent.

exemple de code QuickSelect

si vous voulez utiliser n'importe quelle bibliothèque externe ici est Apache bibliothèque de mathématiques communes en utilisant vous pouvez calculer le médiane .

Pour plus de méthodes et d'utilisation, consultez la documentation API

import org.apache.commons.math3.*;
.....
......
........
//calculate median
public double getMedian(double[] values){
 Median median = new Median();
 double medianValue = median.evaluate(values);
 return medianValue;
}
.......

• Pour en savoir plus sur évaluer la méthode AbstractUnivariateStatistic#évaluer

Mise à jour

calculer dans le programme

en général, la médiane est calculée à l'aide des deux formules données ici

si n est impair alors médiane (m) = valeur de ((n + 1)/2) E terme de l'article.

Si n est égal alors médian (M) = valeur de [(n)/2)E terme de l'article + (n) / 2 + 1) E terme de l'article] / 2

dans votre programme vous avez numArray , d'abord vous devez trier tableau en utilisant tableaux # trier

Arrays.sort(numArray);
int middle = numArray.length/2;
int medianValue = 0; //declare variable 
if (numArray.length%2 == 1) 
    medianValue = numArray[middle];
else
   medianValue = (numArray[middle-1] + numArray[middle]) / 2;

Arrays.sort(numArray);
int middle = ((numArray.length) / 2);
if(numArray.length % 2 == 0){
 int medianA = numArray[middle];
 int medianB = numArray[middle-1];
 median = (medianA + medianB) / 2;
} else{
 median = numArray[middle + 1];
}

EDIT: j'ai d'abord eu medianB paramétrage à middle+1 dans les tableaux de longueurs égales, ce qui était erroné en raison de tableaux de départ compte à 0. Je l'ai mis à jour pour utiliser middle-1 qui est correct et devrait fonctionner correctement pour un tableau avec une longueur égale.

essayez d'abord de trier le tableau. Puis après qu'il est trié, si le tableau a une quantité égale d'éléments la moyenne des deux médians est la médiane, si elle a un nombre impair, l'élément central est la médiane.

utilisez Arrays.sort et puis prenez l'élément du milieu (dans le cas où le nombre n d'éléments dans le tableau est impair) ou prenez la moyenne des deux éléments du milieu (dans le cas n est pair).

  public static long median(long[] l)
  {
    Arrays.sort(l);
    int middle = l.length / 2;
    if (l.length % 2 == 0)
    {
      long left = l[middle - 1];
      long right = l[middle];
      return (left + right) / 2;
    }
    else
    {
      return l[middle];
    }
  }

voici quelques exemples:

  @Test
  public void evenTest()
  {
    long[] l = {
        5, 6, 1, 3, 2
    };
    Assert.assertEquals((3 + 4) / 2, median(l));
  }

  @Test
  public oddTest()
  {
    long[] l = {
        5, 1, 3, 2, 4
    };
    Assert.assertEquals(3, median(l));
  }

et si votre entrée est une Collection , vous pouvez utiliser Google Guava pour faire quelque chose comme ceci:

public static long median(Collection<Long> numbers)
{
  return median(Longs.toArray(numbers)); // requires import com.google.common.primitives.Longs;
}

j'ai fait face à un problème similaire hier. J'ai écrit une méthode avec Java generics afin de calculer la valeur médiane de chaque collection de nombres; vous pouvez appliquer ma méthode aux collections de Doubles, entiers, flotteurs et renvoie un double. S'il vous plaît considérer que ma méthode crée une autre collection afin de ne pas modifier l'original. Je fournis aussi un test, amusez-vous. ;- )

public static <T extends Number & Comparable<T>> double median(Collection<T> numbers){
    if(numbers.isEmpty()){
        throw new IllegalArgumentException("Cannot compute median on empty collection of numbers");
    }
    List<T> numbersList = new ArrayList<>(numbers);
    Collections.sort(numbersList);
    int middle = numbersList.size()/2;
    if(numbersList.size() % 2 == 0){
        return 0.5 * (numbersList.get(middle).doubleValue() + numbersList.get(middle-1).doubleValue());
    } else {
        return numbersList.get(middle).doubleValue();
    }

}

code D'essai de JUnit snippet:

/**
 * Test of median method, of class Utils.
 */
@Test
public void testMedian() {
    System.out.println("median");
    Double expResult = 3.0;
    Double result = Utils.median(Arrays.asList(3.0,2.0,1.0,9.0,13.0));
    assertEquals(expResult, result);
    expResult = 3.5;
    result = Utils.median(Arrays.asList(3.0,2.0,1.0,9.0,4.0,13.0));
    assertEquals(expResult, result);
}

Usage exemple (considérer que le nom de classe est Utils):

List<Integer> intValues = ... //omitted init
Set<Float> floatValues = ... //omitted init
.....
double intListMedian = Utils.median(intValues);
double floatSetMedian = Utils.median(floatValues);

Note: ma méthode fonctionne sur les collections, vous pouvez convertir des tableaux de nombres à la liste des nombres comme indiqué ici

je regardais les mêmes problèmes statistiques. L'approche que vous pensez qu'il est bon et il va fonctionner. (La réponse au tri a été donnée)

mais dans le cas où vous êtes intéressé par la performance de l'algorithme, je pense qu'il y a quelques algorithmes qui ont de meilleures performances que de simplement trier le tableau, un ( QuickSelect ) est indiqué par la réponse de @bruce-feist et est très bien expliqué.

[Java mise en œuvre: https://discuss.leetcode.com/topic/14611/java-quick-select ]

mais il y a une variation de cet algorithme appelé médiane des médianes , vous pouvez trouver une bonne explication sur ce lien: http://austinrochford.com/posts/2013-10-28-median-of-medians.html

Java mise en œuvre de cette: - https://stackoverflow.com/a/27719796/957979

vous pouvez trouver une bonne explication à https://www.youtube.com/watch?time_continue=23&v=VmogG01IjYc

l'idée d'utiliser 2 tas, c'est-à-dire un tas max et un tas moyen.

class Heap {
private Queue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder());
private Queue<Integer> high = new PriorityQueue<>();

public void add(int number) {
    Queue<Integer> target = low.size() <= high.size() ? low : high;
    target.add(number);
    balance();
}

private void balance() {
    while(!low.isEmpty() && !high.isEmpty() && low.peek() > high.peek()) {
        Integer lowHead= low.poll();
        Integer highHead = high.poll();
        low.add(highHead);
        high.add(lowHead);
    }
}

public double median() {
    if(low.isEmpty() && high.isEmpty()) {
        throw new IllegalStateException("Heap is empty");
    } else {
        return low.size() == high.size() ? (low.peek() + high.peek()) / 2.0 : low.peek();
    }
}

}

vérifiez les tableaux.méthodes de tri:

http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html

vous devriez également trouver la médiane dans sa propre méthode abstraite, et juste retourner la valeur à la méthode d'appel. Cela facilitera grandement la mise à l'essai de votre code.

@Aniket a la réponse la plus correcte, mais je changerais une ligne.

median = numArray[middle-1] + Math.abs(numArray[middle-1] - numArray[middle] )/2;

pour deux moyennes additionner à plus de cas int max

public int[] data={31, 29, 47, 48, 23, 30, 21
        , 40, 23, 39, 47, 47, 42, 44, 23, 26, 44, 32, 20, 40};

public double median()
    {
        Arrays.sort(this.data);
        double result=0;
        int size=this.data.length;


        if(size%2==1)
        {
            result=data[((size-1)/2)+1];
            System.out.println(" uneven size : "+result);
        }
        else
        { 
            int middle_pair_first_index =(size-1)/2;
            result=(data[middle_pair_first_index+1]+data[middle_pair_first_index])/2;
            System.out.println(" Even size : "+result);
        }

        return result;
    }

Arrays.sort(numArray);
return (numArray[size/2] + numArray[(size-1)/2]) / 2;