274. H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
Example:
Input:citations = [3,0,6,1,5]
Output: 3 Explanation:[3,0,6,1,5]
means the researcher has5
papers in total and each of them had received3, 0, 6, 1, 5
citations respectively. Since the researcher has3
papers with at least3
citations each and the remaining two with no more than3
citations each, her h-index is3
.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
class Solution { public: int hIndex(vector<int>& citations) { int len = citations.size(); if (len == 0) return 0; vector<int> hash(len+1, 0); int maxIndex = 0; for (int i = 0; i < len; ++i) { if (len <= citations[i]) { hash[len]++; } else { hash[citations[i]]++; } } int paper = 0; for (int i = len; i >= 0; --i) { paper += hash[i]; if (paper >= i) return i; } } };
Runtime: 4 ms, faster than 71.13% of C++ online submissions for H-Index.
tips:
maybe I can understand the intention of this problem.
this is @yfcheng's explanation:
This type of problems always throw me off, but it just takes some getting used to. The idea behind it is some bucket sort mechanisms. First, you may ask why bucket sort. Well, the h-index is defined as the number of papers with reference greater than the number. So assume n
is the total number of papers, if we have n+1
buckets, number from 0 to n, then for any paper with reference corresponding to the index of the bucket, we increment the count for that bucket. The only exception is that for any paper with larger number of reference than n
, we put in the n
-th bucket.
Then we iterate from the back to the front of the buckets, whenever the total count exceeds the index of the bucket, meaning that we have the index number of papers that have reference greater than or equal to the index. Which will be our h-index result. The reason to scan from the end of the array is that we are looking for the greatest h-index. For example, given array [3,0,6,5,1]
, we have 6 buckets to contain how many papers have the corresponding index. Hope to image and explanation help.
相关文章
- Derwent Innovations Index(1963-)--德温特专利索引数据库(Web of Science)
- Using more than one index per table is dangerous?
- 解决list index out of range问题
- ElasticSearch index、mapping、document
- Elasticsearch 使用 Index Pattern 配置
- elasticsearch 创建index 原则
- elasticsearch action.auto_create_index
- QAbstractItemModel使用样例与解析(Model::index使用了createIndex,它会被销毁吗?被销毁了,因为栈对象出了括号就会被销毁)
- thinkphp 5.0 在appache下隐藏index.php入口代码
- 浅析为什么推荐使用唯一不变的 id 作为 key、使用index作为key会导致的问题(复用错误、组件类型propsData或文本node触发重新渲染等问题)
- [LeetCode] H-Index 求H指数
- [LeetCode] 275. H-Index II 求H指数之二
- webpack Entrypoint undefined = index.html