题目描述
一个科学家的 H 指数是其发表的 h 篇论文至少有 h 个引用。根据给定的引用数组，计算一个科学家的 H 指数。
示例 1:
输入: citations = [3,0,6,1,5]
输出: 3
解释: 引用次数大于等于 3 的论文有 3 篇，所以 H 指数是 3。示例 2:
输入: citations = [0,1,3,5,6]
输出: 4题解
这个问题可以通过排序和二分查找来解决，以达到时间复杂度上的优化。首先，我们对引用次数进行排序，然后使用二分查找找到第一个大于等于当前 h 值的引用次数，这个 h 值就是当前的 H 指数。
下面是使用 Go 语言实现的代码：
package main
import (
"fmt"
"sort"
)
func hIndex(citations []int) int {
n := len(citations)
// 对引用次数进行排序
sort.Ints(citations)
// 使用二分查找找到第一个大于等于当前 h 值的引用次数
left, right := 0, n-1
for left <= right {
mid := left + (right-left)/2
if citations[mid] >= n-mid {
// 找到了大于等于 h 的引用次数
return n - mid
}
left = mid + 1
}
// 如果没有找到，则返回 0
return 0
}
func main() {
fmt.Println(hIndex([]int{3,0,6,1,5})) // 输出: 3
fmt.Println(hIndex([]int{0,1,3,5,6})) // 输出: 4
}复杂度分析
- 时间复杂度：O(n log n)，其中 n 是数组
citations的长度。排序的时间复杂度为 O(n log n)。 - 空间复杂度：O(1)，我们只使用了常数级别的额外空间。
