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