Je me demandais s'il était possible de trouver la valeur médiane d'un tableau? Par exemple, supposons que j'ai un tableau de taille neuf. Serait-il possible de trouver l'emplacement du milieu de ce tableau?Trouver la valeur médiane d'un tableau?
En supposant que le réseau x est trié et est de longueur n :
Si n est impair, alors la médiane est X [(n-1)/2].
Si n est même que la médiane est (x [n/2] + x [(n/2) -1])/2.
Cela prendra o (nlogn) temps au moins. – VishAmdi
vector<int> v;
size_t len = v.size;
nth_element(v.begin(), v.begin()+len/2,v.end());
int median = v[len/2];
en Java:
int middleSlot = youArray.length/2;
yourArray[middleSlot];
ou
yourArray[yourArray.length/2];
dans une ligne.
Cela est possible car les tableaux Java ont une taille fixe.
Remarque:3/2 == 1
Ressources:
En C++, vous pouvez utiliser std::nth_element; voir http://cplusplus.com/reference/algorithm/nth_element/.
La réponse ci-dessus Java ne fonctionne que s'il y a est un ammount impair de chiffres ici est la réponse que j'ai obtenu à la solution:
if (yourArray.length % 2 == 0){
//this is for if your array has an even ammount of numbers
double middleNumOne = yourArray[yourArray.length/2 - 0.5]
double middleNumTwo = yourArray[yourArray.length/2 + 0.5]
double median = (middleNumOne + middleNumTwo)/2;
System.out.print(median);
}else{
//this is for if your array has an odd ammount of numbers
System.out.print(yourArray[yourArray.length/2];);
}
Et notez que ceci est une preuve de concept et à la volée. Si vous pensez que vous pouvez le rendre plus compact ou moins intensif, allez-y. S'il vous plaît ne le critiquez pas.
Si vous souhaitez utiliser une bibliothèque externe, voici Apache commons math library en utilisant, vous pouvez calculer le Median.
Pour plus de méthodes et d'utiliser prendre à regarder le API documentation
import org.apache.commons.math3.*;
.....
......
........
//calculate median
public double getMedian(double[] values){
Median median = new Median();
double medianValue = median.evaluate(values);
return medianValue;
}
.......
Calculer dans le programme
En général, la médiane est calculée à l'aide de ce qui suit deux formules given here
Si n est impair alors Médiane (M) = valeur de ((n + 1)/2) terme de l'élément.
Si n est même alors médian (M) = valeur de [((n)/2) ième élément terme + ((n)/2 + 1) ième terme de l'article]/2
Il est très facile comme vous avez 9 éléments (nombre impair).
Recherchez l'élément central d'un tableau.
Dans votre programme, vous pouvez déclarer tableau
//as you mentioned in question, you have array with 9 elements
int[] numArray = new int[9];
alors vous devez trier tableau en utilisant Arrays#sort
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;
Il existe une autre alternative - en général, les suggestions ici soit suggérer le tri du tableau prenant alors la médiane d'un tel tableau ou en s'appuyant sur une solution de bibliothèque (externe). Les algorithmes de tri les plus rapides aujourd'hui sont en moyenne linéaires, mais il est possible de faire mieux que cela aux fins du calcul médian.
L'algorithme le plus rapide pour calculer la médiane à partir d'un tableau non trié est QuickSelect, qui, en moyenne, trouve la médiane dans le temps proportionnelle à O (N). L'algorithme prend array comme argument, avec la valeur int k (la statistique d'ordre, c'est-à-dire le k-ème élément le plus petit dans le tableau). La valeur de k, dans ce cas, est simplement N/2, où N est la longueur du tableau.
La mise en œuvre est peu difficile à obtenir mais voici un exemple qui repose sur l'interface Comparable<T> et Collections.shuffle() sans aucune dépendance externe.
public final class QuickSelectExample {
public static <T extends Comparable<? super T>> T select(T[] a, int k) {
if (k < 1) throw new IllegalStateException("Invalid k - must be in [1, inputLength].");
if (k > a.length) throw new IllegalStateException("K-th element exceeds array length.");
Collections.shuffle(Arrays.asList(a));
return find(a, 0, a.length - 1, k - 1);
}
private static <T extends Comparable<? super T>> T find(T[] a, int lo, int hi, int k) {
int mid = partition(a, lo, hi);
if (k == mid) return a[k];
else if (k < mid) return find(a, lo, mid - 1, k); // search left subarray
else if (k > mid) return find(a, mid + 1, hi, k); // search right subarray
else throw new IllegalStateException("Not found");
}
private static <T extends Comparable<? super T>> int partition(T[] a, int lo, int hi) {
T pivot = a[lo];
int i = lo + 1;
int j = hi;
while (true) { // phase 1
while (i <= hi && (less(a[i], pivot) || eq(a[i], pivot))) // is a[i] >= pivot?
i++;
while (j >= i && !less(a[j], pivot)) // is a[j] <= pivot?
j--;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j); // phase 2
return j;
}
private static <T extends Comparable<? super T>> boolean less(T x, T y) {
return x.compareTo(y) < 0;
}
private static <T extends Comparable<? super T>> boolean eq(T x, T y) {
return x.compareTo(y) == 0;
}
}
Le code produit les statistiques de commande suivantes pour ces tableaux d'entrée:
" Input Array | Actual Output [format: (index k -> array element)] ", //
" | ", //
" [S, O, R, T, E, X, A, M, P, L, E] | [(1 -> A), (2 -> E), (3 -> E), (4 -> L), (5 -> M), (6 -> O), (7 -> P), (8 -> R), (9 -> S), (10 -> T), (11 -> X)] ", //
" [P, A, B, X, W, P, P, V, P, D, P, C, Y, Z] | [(1 -> A), (2 -> B), (3 -> C), (4 -> D), (5 -> P), (6 -> P), (7 -> P), (8 -> P), (9 -> P), (10 -> V), (11 -> W), (12 -> X), (13 -> Y), (14 -> Z)] " //
Faites-en une ligne comme un pro:
return (arr[size/2] + arr[(size-1)/2])/2;
coulé à un double si vous êtes attendre double, etc
Cela devrait être assez trivial si vous savez quelque chose sur la gestion de la matrice. Notez que sauf si le tableau est trié, l'emplacement du milieu n'est pas la médiane. Est-ce que ce sont les devoirs? – teukkam
Java ou C++? Choisissez-en un. Et "valeur médiane" et "tranche moyenne" ne sont pas la même chose, choisissez-en un. – GManNickG