Положение медианы в списке

Question

Положение медианы в списке

У меня есть несортированный массив, и мне нужно положение медианы. Я знаю, что есть несколько алгоритмов для вычисления медианы заданного массива в O (n), но все они включают в себя некоторый вид переупорядочения массива, как в медиане медиан и случайном выборе.

Меня не интересует сам медиана, меня интересует только его положение в массиве.

Есть ли способ сделать это в O (n)? Отслеживание всех свопов создаст огромные накладные расходы, поэтому я ищу другое решение.

2

arrays c++median position

Решение

Другие решения

Вот рабочий пример, который генерирует вторичный массив индексов и находит медиану входного массива через std::nth_element и косвенное сравнение

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <iterator>

int main()
{
// input data, big and expensive to sort or copy
std::string big_data[] = { "hello", "world", "I", "need", "to", "get", "the", "median", "index" };

auto const N = std::distance(std::begin(big_data), std::end(big_data));
auto const M = (N - 1) / 2; // 9 elements, median is 4th element in sorted array

// generate indices
std::vector<int> indices;
auto value = 0;
std::generate_n(std::back_inserter(indices), N, [&](){ return value++; });

// find median of input array through indirect comparison and sorting
std::nth_element(indices.begin(), indices.begin() + M, indices.end(), [&](int lhs, int rhs){
return big_data[lhs] < big_data[rhs];
});
std::cout << indices[M] << ":" << big_data[indices[M]] << "\n";

// check, sort input array and confirm it has the same median
std::sort(std::begin(big_data), std::end(big_data));
std::cout << M << ":" << big_data[M] << "\n";
}

онлайн выход.

Этот алгоритм гарантирован O(N) сложность, так как это сумма std::generate_n а также std::nth_elementоба из которых O(N) в своих входных данных.

1

Существует алгоритм O (n log n) для отслеживания медианы в бесконечном потоке чисел. (Поскольку вы не хотите изменять список, вы можете также рассматривать его как поток.) Алгоритм включает две кучи; один всегда указывает на максимальное число в нижней половине, а другой указывает на минимальное число в верхней половине. Алгоритм объясняется здесь: http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/. Вы можете использовать тот же код с минимальной настройкой.

0

Источник

Accepted Answer

Допустим, у вас есть массив данных, и вы хотите найти его медиану:

double data[MAX_DATA] = ...

Создайте массив индексов и инициализируйте каждый индекс своей позицией, например так:

int index[MAX_DATA];
for (int i = 0 ; i != MAX_DATA ; i++) {
index[i] = i;
}

Теперь реализуем линейный медианный алгоритм со следующими изменениями:

Когда оригинальный алгоритм сравнивает data[i] в data[j]заменить сравнением data[index[i]] в data[index[j]]
Когда оригинальный алгоритм меняет местами data[i] а также data[j], своп index[i] а также index[j] вместо.

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

В C ++ вы можете реализовать это с помощью указателей вместо индексов и использовать std::nth_element на контейнере указателей, вот так:

vector<int> data = {1, 5, 2, 20, 10, 7, 9, 1000};
vector<const int*> ptr(data.size());
transform(data.begin(), data.end(), ptr.begin(), [](const int& d) {return &d;});
auto mid = next(ptr.begin(), data.size() / 2);
nth_element(ptr.begin(), mid, ptr.end(), [](const int* lhs, const int* rhs) {return *lhs < *rhs;});
ptrdiff_t pos = *mid - &data[0];
cout << pos << endl << data[pos] << endl;

Вот ссылка на демо на ideone.

4