indices des k plus grands éléments dans un des ménagères de longueur n de la matrice de

Voici mon application qui fait ce que je veux et je pense que raisonnablement efficace:

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

qui donne de sortie:

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

OriginalL'auteur hazelnusse

Cela devrait être une version améliorée de @hazelnusse qui est exécuté dans le O(nlogk) au lieu de 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

OriginalL'auteur justHelloWorld

De la bibliothèque standard de ne pas obtenir de vous une liste d'indices (il a été conçu pour éviter de passer des données redondantes). Toutefois, si vous êtes intéressé dans les n plus grands éléments, utilisez un certain type de partitionnement (les deux std::partition et std::nth_element O(n)):

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

OriginalL'auteur Richard Pump

Même si le code suivant ne peuvent pas remplir le désiré de la complexité des contraintes, il pourrait être une alternative intéressante pour ladite file d'attente de priorité.

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

OriginalL'auteur Aleph0