h-指数

题目

给你一个整数数组 citations, 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数. 计算并返回该研究者的 h 指数.

根据维基百科上 h 指数的定义: h 代表"高引用次数", 一名科研人员的 h 指数是指他(她)至少发表了 h 篇论文, 并且至少有 h 篇论文被引用次数大于等于 h. 如果 h 有多种可能的值, h 指数是其中最大的那个.

提示:

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

示例

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

输入: citations = [1,3,1]
输出: 1

题解

JavaScript - 排序法

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function (citations) {
  citations.sort((a, b) => b - a)

  for (let i = 0; i < citations.length; i++) {
    // 至少有 i + 1 篇论文的引用次数大于等于 i + 1
    if (citations[i] < i + 1) return i
  }

  return citations.length
}

• 时间复杂度: O(nlogn)
• 空间复杂度: O(1)

JavaScript - 计数法

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function (citations) {
  const n = citations.length
  const count = new Array(n + 1).fill(0)
  for (let i = 0; i < n; i++) {
    if (citations[i] >= n) {
      count[n]++
    } else {
      count[citations[i]]++
    }
  }
  let sum = 0
  for (let i = n; i >= 0; i--) {
    sum += count[i]
    if (sum >= i) {
      return i
    }
  }
  return 0
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)