Поиск Медиана БЕЗ структур данных

Question

(мой код написан на Java, но вопрос в том, агностик, я просто искал идеи алгоритма)

Так вот проблема: я сделал метод, который просто находит медиану набора данных (заданную в виде массива). Вот реализация:

public static double getMedian(int[] numset) { 
    ArrayList<Integer> anumset = new ArrayList<Integer>(); 
    for(int num : numset) { 
     anumset.add(num); 
    } 
    anumset.sort(null); 

    if(anumset.size() % 2 == 0) { 
     return anumset.get(anumset.size()/2); 
    } else { 
     return (anumset.get(anumset.size()/2) 
        + anumset.get((anumset.size()/2) + 1))/2; 
    } 
} 

Учитель в школе, что я иду затем заражал меня написать метод, чтобы найти медиану снова, но без использования каких-либо структур данных. Это включает в себя все, что может содержать более одного значения, так что это включает в себя строки, любые формы массивов и т. Д. Я долгое время пытался даже представить себе идею, и я был в тупике. Есть идеи?

Answer 1

Обычный алгоритм для задачи - это алгоритм выбора Хора. Это в значительной степени похоже на quicksort, за исключением того, что в quicksort вы рекурсивно сортируете как половин после секционирования, но для выбора вы делаете рекурсивный вызов только в разделе, содержащем интересующий объект.

Например, давайте рассмотрим вход, как это, в котором мы собираемся найти четвертый элемент:

[7, 1, 17, 21, 3, 12, 0, 5]

Мы будем произвольно использовать первый элемент (7) в качестве нашего стержня.Мы изначально разделить его, как (с шарниром, отмеченным *:

[1, 3, 0, 5,] * 7, [17, 21, 12]

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

[0] 1 [3, 5] {7, 17, 21, 12}

1 закончил тем, в качестве второго элемента, так что нам нужно разбить детали к его вправо (3 и 5):

{0, 1} 3 [5] {7, 17, 21, 12}

Используя 3 как элемент поворота, мы в конечном итоге ни с чем к слева и 5 направо. 3 - это третий элемент, поэтому нам нужно посмотреть на него справа. Это только один элемент, так что (5) является нашей медианной.

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

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

Это обеспечивает гарантированную сложность O (N).

Answer 2

Sort массив на месте. Возьмите элемент в середине массива, как вы уже делаете. Дополнительного хранения не требуется.

Это займет n log n времени на Java. Лучшее возможное время - линейное (вы должны проверять каждый элемент хотя бы один раз, чтобы обеспечить правильный ответ). Для педагогических целей дополнительное снижение сложности не стоит.

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

Answer 3

Некоторые не очень эффективные идеи:

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

Вы можете улучшить производительность несколько, отслеживая значения min и max до сих пор. Например, если вы уже определили, что 50 слишком велико, чтобы быть медианным, то вы можете пропустить счетный счет через массив для каждого значения, которое больше или равно 50. Аналогично, если вы уже определили, что 25 слишком низко, то вы можете пропустить подсчет проход для каждого значения, которое меньше чем или равно 25.

в C++:

int Median(const std::vector<int> &values) { 
     assert(!values.empty()); 
     const std::size_t half = values.size()/2; 
     int min = *std::min_element(values.begin(), values.end()); 
     int max = *std::max_element(values.begin(), values.end()); 
     for (auto candidate : values) { 
      if (min <= candidate && candidate <= max) { 
       const std::size_t count = 
        std::count_if(values.begin(), values.end(), [&](int x) 
            { return x < candidate; }); 
       if (count == half)  return candidate; 
       else if (count > half) max = candidate; 
       else     min = candidate; 
      } 
     } 
     return min + (max - min)/2; 
    } 

Грозной производительности, но он не использует структуры данных и не изменяет вход массив.