274. H-Index

  • 32.8%

https://leetcode.com/problems/h-index/#/description

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.”

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

  1. An easy approach is to sort the array first.
  2. What are the possible values of h-index?
  3. A faster approach is to use extra space.

方法一:

May.4th

https://leetcode.com/discuss/55969/o-n-time-c-solution-using-hash-table

Line 20: control reaches end of non-void function [-Werror=return-type]

使用vector,index为引用量,值为篇数。时间效率O(n)

注意下面有一处是i–, 不要习惯性的写成i++

根据长度n,最大的为n,由n依次递减查找,O(n)解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty())
return 0;
int n = citations.size();
vector<int> hash(n + 1, 0);
for(int i = 0; i < n; ++i){
if(citations[i] >= n)
hash[n]++;
else
hash[citations[i]]++;
}
int paper = 0;
for(int i = n; i >= 0; --i){
paper += hash[i];
if(paper >= i)
return i;
}
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty()) return 0;
int n = citations.size();
vector<int> v(n+1, 0);
for(auto citation:citations){
if(citation>=n)
v[n]++;
else
v[citation]++;
}
int paper = 0;
for(int i=n; i>=0; i--){
paper += v[i];
if(paper>=i)
return i;
}
}
};

方法二:

直接按定义来,先排序,再依次判断

我的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty()) return 0;
sort(citations.begin(), citations.end(), [](int a, int b){return a>b;});
int paper = 0;
int n = citations.size();
for(; paper<n; paper++){
if(citations[paper]<paper+1)
return paper-1;
}
return paper;
}
};

python


Mine Solution:

48ms, 30.68%, May.4th, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
if not citations: return 0
citations.sort(reverse = True)
for key, value in enumerate(citations):
if key + 1 > value:
return value
elif key + 1 == len(citations) or key + 1 >= citations[key + 1]:
return key + 1

https://discuss.leetcode.com/topic/23810/python-o-n-lgn-time-with-sort-o-n-time-with-o-n-space

Python O(n lgn) time with sort, O(n) time with O(n) space

Sort

1
2
3
4
5
6
7
def hIndex(self, citations):
citations.sort()
n = len(citations)
for i in xrange(n):
if citations[i] >= (n-i):
return n-i
return 0

O(n) space, O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def hIndex(self, citations):
n = len(citations)
citeCount = [0] * (n+1)
for c in citations:
if c >= n:
citeCount[n] += 1
else:
citeCount[c] += 1

i = n-1
while i >= 0:
citeCount[i] += citeCount[i+1]
if citeCount[i+1] >= i+1:
return i+1
i -= 1
return 0

java

4ms, 9.28%, 81 / 81, May.4th, 2016

https://leetcode.com/discuss/55958/my-easy-solution

1
2
3
4
5
6
7
8
9
public class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int len = citations.length;
for(int i=0; i<len; i++)
if(citations[i] >= len - i) return len-i;
return 0;
}
}
谢谢你,可爱的朋友。