Ежедневный бит(е) C++ № 247, Распространенная задача на собеседовании: вычислить индекс Хирша.
Сегодня мы рассмотрим распространенную задачу на собеседовании по C++: вычислить индекс Хирша.
Учитывая информацию о цитировании научных статей в виде std::vector‹int><, где каждый элемент представляет количество цитирований статьи, рассчитайте индекс Хирша: https://en.wikipedia.org /wiki/H-индекс.
Ваше решение должно работать за O(n).
Например, для входных данных {43, 7, 6, 2, 1} результат равен трем, поскольку имеются три статьи с более чем тремя цитированиями.
Прежде чем продолжить чтение, я советую вам попытаться решить эту проблему самостоятельно. Вот ссылка на Compiler Explorer с парой тестовых примеров: https://compiler-explorer.com/z/5K5Wv1ha9.
Решение
Тривиальным решением было бы использовать сортировку и выполнение за O(n*logn).
Поскольку максимально возможный индекс Хирша равен количеству статей, мы можем сократить количество цитирований до citations.size().
Это позволяет нам использовать счетную сортировку.
Мы строим новый массив, содержащий частоты различного количества цитирований, который затем легко обрабатываем, сохраняя условие индекса Хирша.
int h_index(const std::vector<int>& citations) {
// Counting sort: treat any value higher than
// citations.size() as citations.size().
std::vector<int> counts(citations.size()+1, 0);
for (size_t paper : citations)
++counts[std::min(citations.size(), paper)];
// Accumulate the hindex until we reach the condition.
int cnt = 0;
for (int i = std::ssize(counts)-1; i >= 0 && cnt < i; --i)
cnt += std::min(i-cnt, counts[i]);
return cnt;
}
