## 题目描述：

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.

## 解题思路：

h指数综合考虑研究人员的文章篇数与引用次数，来评价其学术成就。

## Python代码：

``````class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
N = len(citations)
cnts = [0] * (N + 1)
for c in citations:
cnts[[c, N][c > N]] += 1
sums = 0
for h in range(N, 0, -1):
if sums + cnts[h] >= h:
return h
sums += cnts[h]
return 0
``````

### 解法II：O(n * logn) 排序 + 遍历

(1)：按照文章引用次数倒序排列，循环遍历数组，统计下标i小于引用次数c的文章篇数即可。

## Python代码：

``````class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
for i, c in enumerate(sorted(citations, reverse = True)):
if i >= c:
return i
return len(citations)
``````

## Python代码：

``````class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
return sum(i < c for i, c in enumerate(sorted(citations, reverse = True)))
``````

(2)：按照文章引用次数正序排列，循环遍历数组，统计min(引用次数c, 剩余文章篇数N-i)的最大值

## Python代码：

``````class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
N = len(citations)
for i, c in enumerate(sorted(citations)):
if N - i <= c:
return N - i
return 0
``````

## Python代码：

``````class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
return max(min(c, len(citations) - i)
for i, c in enumerate(sorted(citations) + [0]))
``````

Pingbacks已关闭。

1. Tina 发布于 2016年6月5日 09:37 #

解法二是O（n+logn） 吧？

2. 在线疯狂 发布于 2016年6月8日 20:46 #

排序的复杂度是O(n * log n)