212. Citation Index
A researcher has written several papers. The array citations holds the number of times each paper has been cited. The researcher's citation index is the largest number h such that at least h of the papers have each been cited at least h times.
Return the citation index. The index is never larger than the number of papers, and it is 0 when not even a single paper has been cited. For example, if the citation counts are [6, 6, 6, 1], then three papers have at least 3 citations each, but there are not four papers with at least 4 citations, so the index is 3.
A researcher can have up to 20,000 papers, so trying every possible h against the whole list is too slow.
Example 1
- Input:
- citations = [10,4,4,0,7,2]
- Output:
- 4
- Explanation:
Four papers (10, 7, 4, 4) have at least 4 citations each. Five papers with at least 5 citations do not exist, so the answer is 4.
Example 2
- Input:
- citations = [0,0,0]
- Output:
- 0
- Explanation:
No paper has been cited, so the index is 0.
Example 3
- Input:
- citations = [8,1,12,2,2,8,3]
- Output:
- 3
- Explanation:
Three papers (12, 8, 8) have at least 3 citations. There are not four papers with at least 4, so the answer is 3.
Constraints
1 ≤ citations.length ≤ 20000
0 ≤ citations[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)