индексы k наибольших элементов в массиве unsorted length n

Question

Мне нужно найти индексы k наибольших элементов несортированного длины n, array/vector в C++, k < n. Я видел, как использовать nth_element() для поиска k-й статистики, но я не уверен, что использование этого является правильным выбором для моей проблемы, поскольку мне кажется, что мне нужно будет сделать k вызовов nth_statistic, что, я думаю у него будет сложность O (kn), которая может быть такой же хорошей, как она может быть получена? Или есть способ сделать это только в O (n)?

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

Есть ли что-нибудь в стандартной библиотеке C++, которая делает это одним лайнером или любым умным способом реализовать это самостоятельно всего за пару строк? В моем конкретном случае k = 3 и n = 6, поэтому эффективность не вызывает большого беспокойства, но было бы неплохо найти чистый и эффективный способ сделать это при любых k и n.

Похоже, что Mark the top N elements of an unsorted array - это, вероятно, самая близкая публикация, которую я могу найти на SO, сообщения есть в Python и PHP.

Answer 1

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

Это упоминается как "быстрый выбор" и here is a C++ implementation:

int partition(int* input, int p, int r) 
{ 
    int pivot = input[r]; 

    while (p < r) 
    { 
     while (input[p] < pivot) 
      p++; 

     while (input[r] > pivot) 
      r--; 

     if (input[p] == input[r]) 
      p++; 
     else if (p < r) { 
      int tmp = input[p]; 
      input[p] = input[r]; 
      input[r] = tmp; 
     } 
    } 

    return r; 
} 

int quick_select(int* input, int p, int r, int k) 
{ 
    if (p == r) return input[p]; 
    int j = partition(input, p, r); 
    int length = j - p + 1; 
    if (length == k) return input[j]; 
    else if (k < length) return quick_select(input, p, j - 1, k); 
    else return quick_select(input, j + 1, r, k - length); 
} 

int main() 
{ 
    int A1[] = { 100, 400, 300, 500, 200 }; 
    cout << "1st order element " << quick_select(A1, 0, 4, 1) << endl; 
    int A2[] = { 100, 400, 300, 500, 200 }; 
    cout << "2nd order element " << quick_select(A2, 0, 4, 2) << endl; 
    int A3[] = { 100, 400, 300, 500, 200 }; 
    cout << "3rd order element " << quick_select(A3, 0, 4, 3) << endl; 
    int A4[] = { 100, 400, 300, 500, 200 }; 
    cout << "4th order element " << quick_select(A4, 0, 4, 4) << endl; 
    int A5[] = { 100, 400, 300, 500, 200 }; 
    cout << "5th order element " << quick_select(A5, 0, 4, 5) << endl; 
} 

ВЫВОД:

1st order element 100 
2nd order element 200 
3rd order element 300 
4th order element 400 
5th order element 500 

EDIT

Эта конкретная реализация имеет О (п) среднее время выполнения; из-за метода выбора стержня он обменивается наихудшим временем работы quicksort. К optimizing the pivot choice, ваш худший случай также будет O (n).

Answer 2

Стандартная библиотека не даст вам список индексов (он был разработан, чтобы не пропускать избыточные данные). Тем не менее, если вы заинтересованы в п крупнейших элементов, использовать какое-то разбиение (как std::partition и std::nth_element являются O (п)):

#include <iostream> 
#include <algorithm> 
#include <vector> 

struct Pred { 
    Pred(int nth) : nth(nth) {}; 
    bool operator()(int k) { return k >= nth; } 
    int nth; 
}; 

int main() { 

    int n = 4; 
    std::vector<int> v = {5, 12, 27, 9, 4, 7, 2, 1, 8, 13, 1}; 

    // Moves the nth element to the nth from the end position. 
    std::nth_element(v.begin(), v.end() - n, v.end()); 

    // Reorders the range, so that the first n elements would be >= nth. 
    std::partition(v.begin(), v.end(), Pred(*(v.end() - n))); 

    for (auto it = v.begin(); it != v.end(); ++it) 
     std::cout << *it << " "; 
    std::cout << "\n"; 

    return 0; 
} 

Answer 3

Вот моя реализация, которая делает то, что я хочу, и я думаю, что это разумно эффективная:

#include <queue> 
#include <vector> 
// maxindices.cc 
// compile with: 
// g++ -std=c++11 maxindices.cc -o maxindices 
int main() 
{ 
    std::vector<double> test = {0.2, 1.0, 0.01, 3.0, 0.002, -1.0, -20}; 
    std::priority_queue<std::pair<double, int>> q; 
    for (int i = 0; i < test.size(); ++i) { 
    q.push(std::pair<double, int>(test[i], i)); 
    } 
    int k = 3; // number of indices we need 
    for (int i = 0; i < k; ++i) { 
    int ki = q.top().second; 
    std::cout << "index[" << i << "] = " << ki << std::endl; 
    q.pop(); 
    } 
} 

, который дает выход:

index[0] = 3 
index[1] = 1 
index[2] = 0 

Answer 4

вопрос имеет частичный ответ; то есть std::nth_element возвращает «n-аю статистику» со свойством, которое ни один из элементов, предшествующих n-му, больше, чем он, и Ни один из следующих ниже элементов ниже.

Таким образом, всего одного звонка до std::nth_element достаточно, чтобы получить наибольшие элементы k. Сложность времени будет O (n), которая теоретически является самой маленькой, так как вы должны посетить каждый элемент хотя бы один раз, чтобы найти наименьший (или в этом случае k-самый маленький) элемент (ы). Если вам нужно, чтобы эти k элементов были заказаны, вам необходимо заказать их, которые будут O (k log (k)). Итак, в общем случае O (n + k log (k)).

Answer 5

Это должно быть улучшенный вариант @hazelnusse, который выполнен в O(nlogk) вместо O(nlogn)

#include <queue> 
#include <iostream> 
#include <vector> 
// maxindices.cc 
// compile with: 
// g++ -std=c++11 maxindices.cc -o maxindices 
int main() 
{ 
    std::vector<double> test = {2, 8, 7, 5, 9, 3, 6, 1, 10, 4}; 
    std::priority_queue< std::pair<double, int>, std::vector< std::pair<double, int> >, std::greater <std::pair<double, int> > > q; 
    int k = 5; // number of indices we need 
    for (int i = 0; i < test.size(); ++i) { 
    if(q.size()<k) 
     q.push(std::pair<double, int>(test[i], i)); 
    else if(q.top().first < test[i]){ 
     q.pop(); 
     q.push(std::pair<double, int>(test[i], i)); 
    } 
    } 
    k = q.size(); 
    std::vector<int> res(k); 
    for (int i = 0; i < k; ++i) { 
    res[k - i - 1] = q.top().second; 
    q.pop(); 
    } 
    for (int i = 0; i < k; ++i) { 
    std::cout<< res[i] <<std::endl; 
    } 
} 

Answer 6

Вы можете сделать это в O(n) время с расчетным счетом:

• Пусть r Б.Е. k -го порядка Статистика
• Initialize две пустые списки bigger и equal.
• Для каждого индекса i:
  • Если array[i] > r, добавить i к bigger
  • Если array[i] = r, добавьте i в equal
• Отброс элементы equal пока сумма длин двух списков is k
• Возврат конкатенации двух списков.

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

Answer 7

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

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

std::vector<int> largestIndices(const std::vector<double>& values, int k) { 
    std::vector<int> ret; 

    std::vector<std::pair<double, int>> q; 
    int index = -1; 
    std::transform(values.begin(), values.end(), std::back_inserter(q), [&](double val) {return std::make_pair(val, ++index); }); 
    auto functor = [](const std::pair<double, int>& a, const std::pair<double, int>& b) { return b.first > a.first; }; 
    std::make_heap(q.begin(), q.end(), functor); 
    for (auto i = 0; i < k && i<values.size(); i++) { 
     std::pop_heap(q.begin(), q.end(), functor); 
     ret.push_back(q.back().second); 
     q.pop_back(); 
    } 

    return ret; 
} 

int main() 
{ 
    std::vector<double> values = { 7,6,3,4,5,2,1,0 }; 
    auto ret=largestIndices(values, 4); 
    std::copy(ret.begin(), ret.end(), std::ostream_iterator<int>(std::cout, "\n")); 
}