題目描述：
給定一位研究者論文被引用次數(shù)的數(shù)組（被引用次數(shù)是非負(fù)整數(shù)）。編寫一個方法，計算出研究者的 h 指數(shù)。
h 指數(shù)的定義: “h 代表“高引用次數(shù)”（high citations），一名科研人員的 h 指數(shù)是指他（她）的 （N 篇論文中）至多有 h 篇論文分別被引用了至少 h 次。（其余的 N - h 篇論文每篇被引用次數(shù)不多于 h 次。）”
示例:
輸入: citations = [3,0,6,1,5]
輸出: 3
解釋: 給定數(shù)組表示研究者總共有 5 篇論文，每篇論文相應(yīng)的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇論文每篇至少被引用了 3 次，其余兩篇論文每篇被引用不多于 3 次，所以她的 h 指數(shù)是 3。
說明:
如果 h 有多種可能的值，h 指數(shù)是其中最大的那個。
解答思路1
對數(shù)據(jù)進(jìn)行排序，當(dāng)索引i位置的值大于N-i(即包含所處位置以及后面數(shù)據(jù)的個數(shù))時，滿足條件。
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
count = len(citations)
citations.sort()
temp = float('-inf')
for i in range(count):
if citations[i] >= count - i:
temp = max(temp, count - i)
if temp != float('-inf'):
return temp
else:
return 0
解答思路2（計數(shù)）
源自官方解答：https://leetcode-cn.com/problems/h-index/solution/hzhi-shu-by-leetcode/
分析
基于比較的排序算法存在時間復(fù)雜度下界 O(n\log n)O(nlogn)，如果要得到時間復(fù)雜度更低的算法，就必須考慮不基于比較的排序。
算法
方法一中，我們通過降序排序得到了 hh 指數(shù)，然而，所有基于比較的排序算法，例如堆排序，合并排序和快速排序，都存在時間復(fù)雜度下界 O(nlogn)。要得到時間復(fù)雜度更低的算法. 可以考慮最常用的不基于比較的排序，計數(shù)排序。
然而，論文的引用次數(shù)可能會非常多，這個數(shù)值很可能會超過論文的總數(shù) nn，因此使用計數(shù)排序是非常不合算的（會超出空間限制）。在這道題中，我們可以通過一個不難發(fā)現(xiàn)的結(jié)論來讓計數(shù)排序變得有用，即：
如果一篇文章的引用次數(shù)超過論文的總數(shù) n，那么將它的引用次數(shù)降低為 n 也不會改變 h 指數(shù)的值。
由于 h 指數(shù)一定小于等于 n，因此這樣做是正確的。在直方圖中，將所有超過 y 軸值大于 n 的變?yōu)?n 等價于去掉 y>n 的整個區(qū)域。
從直方圖中可以更明顯地看出結(jié)論的正確性，將 y>n 的區(qū)域去除，并不會影響到最大的正方形，也就不會影響到 h 指數(shù)。
我們用一個例子來說明如何使用計數(shù)排序得到 h 指數(shù)。首先，引用次數(shù)如下所示：
citations=[1, 3, 2, 3, 100]將所有大于 n=5 的引用次數(shù)變?yōu)?n，得到：
citations = [1, 3, 2, 3, 5]計數(shù)排序得到的結(jié)果如下：
| k | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| count | 0 | 1 | 1 | 2 | 0 | 1 |
| s_k | 5 | 5 | 4 | 3 | 1 | 1 |
其中 s_k 表示至少有 k 次引用的論文數(shù)量，在表中即為在它之后的列（包括本身）的 count 一行的和。根據(jù)定義，最大的滿足 k ≤ s_k 的 k 即為所求的 h。在表中，這個 k 為 3，因此 h 指數(shù)為 3。
public class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int[] papers = new int[n + 1];
// 計數(shù)
for (int c: citations)
papers[Math.min(n, c)]++;
// 找出最大的 k
int k = n;
for (int s = papers[n]; k > s; s += papers[k])
k--;
return k;
復(fù)雜度分析
時間復(fù)雜度：O(n)。在計數(shù)時，我們僅需要遍歷 citations 數(shù)組一次，因此時間復(fù)雜度為 O(n)。在找出最大的 k 時，我們最多需要遍歷計數(shù)的數(shù)組一次，而計數(shù)的數(shù)組的長度為 O(n)，因此這一步的時間復(fù)雜度為 O(n)，即總的時間復(fù)雜度為 O(n)。
空間復(fù)雜度：O(n)。我們需要使用 O(n) 的空間來存放計數(shù)的結(jié)果。
