Позиция медианы в списке

Question

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

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

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

Answer 1

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

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; 

Вот link to a demo on ideone.

Answer 2

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

Answer 3

Вот пример работы, который генерирует вторичный массив индексов, и находит медиану входного массива через 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"; 
} 

Интернет output.

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