Znaleźć medianę tablicy?

Question

Zastanawiam się, czy udało się znaleźć medianę tablicy? Załóżmy na przykład, że mam tablicę o rozmiarze dziewiątym. Czy możliwe byłoby znalezienie środkowej szczeliny tej tablicy?

Answer 1

Zakładając, że układ x sortowane i długości n:

Jeżeli n jest liczbą nieparzystą wówczas mediana x [(N-1)/2].
Jeśli n jest parzyste niż mediana (x [n/2] + x [(n/2) -1])/2.

Answer 2

vector<int> v; 
size_t len = v.size; 
nth_element(v.begin(), v.begin()+len/2,v.end()); 

int median = v[len/2]; 

Answer 3

w Javie:

int middleSlot = youArray.length/2; 
yourArray[middleSlot]; 

lub

yourArray[yourArray.length/2]; 

w jednej linii.

Jest to możliwe, ponieważ w macierzach java mają stały rozmiar.

UWAGA:3/2 == 1

---

Zasoby:

• Java tutorial - Arrays

Answer 4

W C++ można użyć std::nth_element; patrz http://cplusplus.com/reference/algorithm/nth_element/.

Answer 5

Powyższa odpowiedź w języku Java działa tylko w przypadku występowania nieparzystej liczby tutaj podano odpowiedź na to pytanie:

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

Należy zauważyć, że jest to dowód na to, że pomysł został wykonany i jest w trakcie pracy. Jeśli uważasz, że możesz sprawić, że będzie bardziej kompaktowy lub mniej intensywny, idź przed siebie. Nie krytykuj go.

Answer 6

Jeśli chcesz użyć dowolnej biblioteki zewnętrznej, tutaj jest Apache commons math library, za pomocą której można obliczyć wartość Median.
Więcej metod i używać wziąć spojrzeć na 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; 
} 
....... 

• Więcej informacji na temat oceny sposobu AbstractUnivariateStatistic#evaluate

Oblicz w programie

Generalnie średnia jest obliczana za pomocą następującego dwie formuły given here

Jeśli n jest nieparzyste, to Median (M) = wartość ((n + 1)/2) th termin pozycji.
Jeżeli n jest nawet wtedy Mediana (M) = wartość [((n)/2), H perspektywie elementu + ((n)/2 + 1) -ej elementu termin]/2

Bardzo łatwe, ponieważ masz 9 elementów (liczba nieparzysta).
Znajdź środkowy element tablicy.
W programie można zadeklarować tablicę

//as you mentioned in question, you have array with 9 elements 
int[] numArray = new int[9]; 

to trzeba posortować tablicę używając 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; 

Answer 7

Jest jeszcze inna alternatywa - w ogóle, sugestie tutaj albo zaproponować sortowania tablicy następnie podjęciem mediana z takiej tablicy lub polegająca na rozwiązaniu (zewnętrznej) biblioteki. Najszybsze obecnie algorytmy sortowania są średnio liniowe, ale można to zrobić lepiej niż przy obliczaniu mediany.

Najszybszym algorytmem obliczania mediany z nieposortowanej tablicy jest QuickSelect, która średnio znajduje medianę w czasie proporcjonalnym do O (N). Algorytm przyjmuje tablicę jako argument wraz z wartością int k (statystyka zamówienia, tj. K-ty najmniejszy element w tablicy). Wartość k, w tym przypadku, jest po prostu N/2, gdzie N jest długością tablicy.

Implementacja jest trochę skomplikowana, aby uzyskać prawo, ale tutaj jest przykład, który opiera się na interfejsie Comparable<T> i Collections.shuffle() bez żadnych zewnętrznych zależności.

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

Kod produkuje następujące statystyki zamówienie na tych tablic wejściowych:

  "     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)]   " // 

Answer 8

zrobić w jednej linii jak profesjonalista:

return (arr[size/2] + arr[(size-1)/2])/2; 

obsady do double jeśli jesteś oczekiwanie na double, itp.