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

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

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

Это должна быть улучшенная версия @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;
}
}

8
4
1
2
6

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

Это упоминается как «быстрый выбор» и здесь реализация C ++:

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

РЕДАКТИРОВАТЬ

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

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

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

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

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

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

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

#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"));
}