Как вычислить медиану массива?

Ответ 1

Класс Arrays в Java имеет статическую функцию сортировки, которую вы можете вызвать с помощью Arrays.sort(numArray).

Arrays.sort(numArray);
double median;
if (numArray.length % 2 == 0)
    median = ((double)numArray[numArray.length/2] + (double)numArray[numArray.length/2 - 1])/2;
else
    median = (double) numArray[numArray.length/2];

Ответ 2

Сортировка массива не нужна и неэффективна. Существует вариант алгоритма QuickSort (QuickSelect), который имеет среднее время выполнения O (n); если вы сначала отсортируете, вы опуститесь до O (n log n). Он на самом деле находит n-й наименьший элемент в списке; для медианы, вы просто используете n = половину длины списка. Позвольте называть его quickNth (list, n).

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

Разделите исходный список на три небольших списка:

• Один со значениями, меньшими, чем точка поворота.
• Один со значениями, равными оси.
• И один со значениями, большими, чем точка поворота.

У вас есть три случая:

• В "меньшем" списке есть >= n элементов. В этом случае вы знаете, что в этом списке находится n-е наименьшее число. Верните quickNth (меньше, n).
• В меньшем списке есть < n, но сумма длин меньшего и равного списков имеет >= n элементов. В этом случае nth равно любому элементу в "равном" списке; вы закончили.
• n больше суммы длин меньшего и равного списков. В этом случае вы можете существенно пропустить эти два и соответственно отрегулировать n. Возврат quickNth (больше, n - длина (меньше) - длина (равная)).

Готово.

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

Если вам очень не повезло с вашим выбором опорных точек, и вы всегда выбираете наименьшее или самое высокое значение в качестве вашего поворота, это занимает время O (n ^ 2); это плохо. Но, это также очень маловероятно, если вы выберете свой стержень с достойным алгоритмом.

Пример кода QuickSelect

Ответ 3

Если вы хотите использовать любую внешнюю библиотеку, Apath commons math library, вы можете вычислить Median.
Дополнительные методы и использование см. В документации

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

• Подробнее о методе оценки AbstractUnivariateStatistiС# оценить

Обновить

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

Как правило, медиана рассчитывается с использованием следующих двух формул здесь

Если n нечетно, то Median (M) = значение ((n + 1)/2) -го члена элемента.
Если n равно, то Median (M) = значение [((n)/2) -го члена элемента + ((n)/2 + 1) -го члена элемента]/2

В вашей программе у вас есть numArray, сначала вам нужно отсортировать массив, используя 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;

Ответ 4

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: у меня первоначально была medianB установка middle+1 в массивах четной длины, это было неправильно из-за того, что начальный счет массива равен 0. Я обновил его, чтобы использовать middle-1, который является правильным и должен работать правильно для массив с четной длиной.

Ответ 5

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

Ответ 6

Используйте Arrays.sort, а затем возьмите средний элемент (если число n элементов в массиве нечетное) или возьмите среднее из двух средних элементов (в случае n четное).

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

Вот несколько примеров:

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

И если ваш ввод Collection, вы можете использовать Google Guava, чтобы сделать что-то вроде этого:

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

Ответ 7

Я столкнулся с аналогичной проблемой вчера. Я написал метод с дженериками Java, чтобы вычислить медианное значение каждой коллекции чисел; вы можете применить мой метод к коллекциям двойников, целых чисел, поплавков и возвращает двойной. Учтите, что мой метод создает другую коллекцию, чтобы не изменять исходную. Я предоставляю также тест, получаю удовольствие.; -)

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

}

Сводный фрагмент кода JUnit:

/**
 * 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);
}

Пример использования (рассмотрим имя класса Utils):

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

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

Ответ 8

Я рассматривал те же проблемы статистики. Подход, который вы думаете, хорош, и он будет работать. (Ответ на сортировку был дан)

Но если вас интересует производительность алгоритма, я думаю, что есть несколько алгоритмов, которые имеют лучшую производительность, чем просто сортировка массива, одна (QuickSelect) обозначается ответом @bruce-feist и очень хорошо объясняется.

[Реализация Java: https://discuss.leetcode.com/topic/14611/java-quick-select]

Но есть вариация этого алгоритма с именем медиана медианов, вы можете найти хорошее объяснение по этой ссылке: http://austinrochford.com/posts/2013-10-28-median-of-medians.html

Java-реализация:  - fooobar.com/questions/184731/...

Ответ 9

Вы можете найти хорошее объяснение на https://www.youtube.com/watch?time_continue=23&v=VmogG01IjYc

Идея в том, чтобы использовать 2 кучи, а именно одну максимальную кучу и среднюю кучу.

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

}

Ответ 10

Ознакомьтесь с методами Arrays.sort:

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

Вы также должны действительно абстрагироваться от поиска медианного в свой собственный метод и просто вернуть значение вызывающему методу. Это упростит тестирование кода.

Ответ 11

@Aniket имеет самый правильный ответ, но я бы изменил строку.

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

для двух средних значений, содержащих больше, чем int max.

Ответ 12

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

Ответ 13

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

Ответ 14

И никто не обращает внимания, когда список содержит только один элемент (list.size == 1). Все ваши ответы потерпят крах с индексом вне привязанного исключения, потому что целочисленное деление возвращает ноль (1/2 = 0). Правильный ответ (в Котлине):

MEDIAN("MEDIAN") {

        override fun calculate(values: List<BigDecimal>): BigDecimal? {
            if (values.size == 1) {
                return values.first()
            }
            if (values.size > 1) {
                val valuesSorted = values.sorted()
                val mid = valuesSorted.size / 2
                return if (valuesSorted.size % 2 != 0) {
                    valuesSorted[mid]
                } else {
                    AVERAGE.calculate(listOf(valuesSorted[mid - 1], valuesSorted[mid]))
                }
            }
            return null
        }
    },