Daily bit(e) of C++ | Calculate h-index
Daily bit(e) of C++ #247, Common interview problem: Calculate h-index.
Today, we will look at a common C++ interview problem: Calculate h-index.
Given information about research paper citations as std::vector<int>, where each element represents the number of citations for a paper, calculate the h-index: https://en.wikipedia.org/wiki/H-index.
Your solution should run in O(n).
For example, for the input {43, 7, 6, 2, 1}, the result is three, because there are three papers with more than three citations.
Before you continue reading, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/5K5Wv1ha9.
Solution
A trivial solution would use sorting and run in O(n*logn).
Because the maximum possible h-index equals the number of papers, we can truncate the number of citations to citations.size().
This allows us to use a counting sort.
We construct a new array containing the frequencies of different numbers of citations, which we can then easily process while maintaining the h-index condition.
