T274

整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：

1
2
3
4
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：

1
2
输入：citations = [1,3,1]
输出：1

分析一下，根据定义，我们可以从中读出什么？

  1. n = citations.size是研究者的论文总数目
  2. h 的范围是 0 到 n
  3. 结果与citations[i]中元素顺序无关，意味着可以排序

让我们先把复杂度抛到一边，写出一个硬解，感受一下。 由于提到了“至少 有 h 篇论文被引用次数大于等于 h ”，可以联想到"y=x"这种直线对可行域进行划分。简单思考后可以写出这样的代码：

1
2
3
4
5
6
7
8
9
fun hIndex(citations: IntArray): Int {
        citations.sortDescending()
        val size = citations.size
        var ans = 0
        while (ans<size && citations[ans]>ans){
            ans++
        }
        return ans
    }

首先，对传入的 citations 数组进行降序排序。这样排序后，索引 i 处的值 citations[i] 表示至少被引用了 citations[i] 次的论文数量。

ans 指的是计算得到的H指数，初始化为0。

开始循环，citations[ans] > ans表示当前论文引用次数大于 ans，这意味着至少有 ans 篇论文被引用了 ans 次以上。循环递增 ans 的值，直到找到最大的 ans 满足条件，即 citations[ans] <= ans 为止。

将论文的引用次数进行排序，然后从最大的引用次数开始逐步减小，找到最大的 ans 满足 citations[ans] <= ans 的条件，即为H指数

这里用到了排序，时间复杂度是O(logN)，有没有办法把复杂度降低到O(N)？去掉排序，我们不妨用空间换时间，用另一个数组count[i]存储论文的被引用次数。具体含义是，count[i]=a表示的是被引用i次的论文一共有a篇。那这个数组中最大的下标就是citations[i]中最大的元素值：citations.max()。

1
2
3
4
5
6
7
8
9
10
11
12
13
fun hIndex(citations: IntArray):Int{
    var total = 0
    val count = IntArray(citations.max()+1){0}
    val countSize = count.size
    for(number in citations){
        count[number]++
    }
    for (n in countSize-1 downTo 0){
        total += count[n]
        if (total>= n) return n
    }
    return -1
}

total 用于累计被引用次数大于等于当前检查的引用次数的论文数量。

使用逆序的 for 循环，从 countSize - 1（即数组最后一个索引）开始向前遍历 count 数组。

在每一次迭代中，将 total 增加 count[n]，表示将当前引用次数为 n 的论文数量加入到 total 中。

然后检查 total 是否大于等于 n，如果满足，则说明找到了H指数，即 n，直接返回 n。

如果循环结束后仍未找到符合条件的 n，则返回 -1，表示未找到合适的H指数。

这样，复杂度降低到了O(N)。

当然，作为Kotlin的使用者，你还可以写的更加优雅：

1
2
3
4
5
6
7
8
9
10
fun hIndex(citations: IntArray): Int {
    val count = IntArray(citations.maxOrNull() ?: 0 + 1) { 0 }
    citations.forEach { count[it]++ }
		var total = 0
		for (n in count.indices.reversed()) {
    	total += count[n]
    	if (total >= n) return n
		}
		return -1
}