Поиск медианного значения массива?

Question

Мне было интересно, можно ли найти медианное значение массива? Например, предположим, что у меня есть массив размером девять. Можно ли найти средний слот этого массива?

Answer 1

Предполагая, что массив х сортируется и имеет длину п:

Если п нечетно, то медиана х [(п-1)/2].
Если п четно, чем медиана (х [п/2] + х [(п/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

В Java:

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

или

yourArray[yourArray.length/2]; 

в одной строке.

Это возможно, потому что в массивах java есть фиксированный размер.

Примечание:3/2 == 1

---

Ресурсы:

• Java tutorial - Arrays

Answer 4

В C++, вы можете использовать std::nth_element; см. http://cplusplus.com/reference/algorithm/nth_element/.

Answer 5

Ответ на Java выше, работает только если есть нечетная сумма из номера здесь ответ я получил решение:

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

и заметьте, что это доказательство концепции и от мухи. Если вы считаете, что можете сделать его более компактным или менее интенсивным, пойдите прямо вперед. Пожалуйста, не критикуйте его.

Answer 6

Если вы хотите использовать любую внешнюю библиотеку, здесь Apache commons math library с помощью вы можете рассчитать Median.
Для более методов и использовать берут смотреть на 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; 
} 
....... 

• Более подробная информация по оценке метода AbstractUnivariateStatistic#evaluate

Пересчитать в программе

Вообще, медиана рассчитывается по следующей формуле две формулы: given here

Если n нечетно, то медиана (M) = значение ((n + 1)/2) -го члена.
Если п четно, то медиана (М) = значение [((N)/2) -го члена пункт + ((п)/2 + 1) -й член пункт]/2

Это очень легко, поскольку у вас есть 9 элементов (нечетное число).
Найти средний элемент массива.
В вашей программе вы можете объявить массив

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

, то вам нужно отсортировать массив с помощью 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

Существует еще одна альтернатива - в общем, предложения здесь либо предложить сортировку массива, то взяв медиана из такого массива или полагающаяся на (внешнее) библиотечное решение. Самые быстрые алгоритмы сортировки сегодня являются в среднем линейными, но для целей медианного расчета можно сделать лучше, чем это.

Самый быстрый алгоритм вычисления медианы из несортированного массива - QuickSelect, который в среднем находит медиану по времени, пропорциональную O (N). Алгоритм принимает массив как аргумент вместе с значением int k (статистика порядка, то есть k-й наименьший элемент в массиве). Значение k, в данном случае, просто N/2, где N - длина массива.

Реализация немного сложна, чтобы получить право, но вот пример, который основан на интерфейсе Comparable<T> и Collections.shuffle() без каких-либо внешних зависимостей.

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

код производит следующую статистику заказов для этих входных массивов:

  "     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

Делают это в одну линию, как профи:

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

бросок к double если вы ожидая double и т. д.