Advertisement
bogolyubskiyalexey

Untitled

Dec 8th, 2020
742
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. Реализовать функцию top_k, которая получает на вход итератор начала и конца на контейнер и количество искомых элементов k, функция возвращает вектор из k элементов - самых больших значений из переданного контейнера, если в контейнере меньше элементов, чем k, то надо вернуть все элементы. В результирующем векторе данные должны быть отсортированы от большего к меньшему.
  2. Ограничения:
  3.  - время выполнения O(N*logK), N = std::distance(first, last)
  4.  - доп память O(K)
  5.  - для значений в контейнере гарантируется наличие оператора меньше и конструктора копирования.
  6. Примеры использования
  7. std::vector<int> a = {9, 5,1, 4,10};
  8. std::vector<int> resultA = top_k(a.begin(), a.end(), 3); // 10, 9, 5
  9. std::list<float> b = {0.5, 1.0, -1.0};
  10. std::vector<float> resultB = top_k(b.begin(), b.end(), 10); // 1.0, 0.5, -1.0
  11. std::set<int> c = {1, 2, 3, 4, 5, 6};
  12. std::vector<int> resultC = top_k(c.cbegin(), c.cend(), 4); // 6, 5, 4, 3
  13. struct MyType {
  14.      int value;
  15.      MyType(int);
  16.      MyType(const MyType& other);
  17.      bool operator< (const MyType& other) const;
  18. }
  19. std::vector<MyType> d = {1, 10, 5};
  20. std::vector<MyType> resultD = top_k(d.begin(), d.end(), 1); // 10
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement