274. H 指数（JS实现）

不念不忘少年蓝@ 2022-11-27 15:50 114阅读 0赞

## 1 题目 ##

> 给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。  
> h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）  
> 例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。  
> 示例：  
> 输入：citations = \[3,0,6,1,5\]  
> 输出：3  
> 解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。  
> 由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

链接：https://leetcode-cn.com/problems/h-index

## 2 思路 ##

**这道题我先将因子进行排序，然后用二分法将目标数和其到数组尾的长度进行对比即可，题解里用计数排序，可以进一步降低时间复杂度：  
论文的引用次数可能会非常多，这个数值很可能会超过论文的总数 n，因此使用计数排序是非常不合算的（会超出空间限制）。在这道题中，我们可以通过一个不难发现的结论来让计数排序变得有用，即如果一篇文章的引用次数超过论文的总数 n，那么将它的引用次数降低为 n也不会改变 h指数的值。排序后再使用二分即可得到正确答案**

## 3代码 ##

/** * @param {number[]} citations * @return {number} */
    var hIndex = function(citations) { 
     if (citations.length === 0) return 0;
    
      citations.sort((a,b) => a - b);    //先将因子排序
    
      let low = 0;
      let high = citations.length - 1;
    
      while(low <= high) {      //使用二分法，将每次的结果与长度进行对比
        let mid = Math.floor((low + high) / 2);
        let len = citations.length - mid;
    
        if (citations[mid] < len) { 
          low = mid + 1;
        } else if (citations[mid] > len) { 
          if (mid > 0 && citations[mid-1] <= len || mid === 0) { 
            return len;
          } else { 
            high = mid - 1;
          }
        } else { 
          return len;
        }
      }
    
      return 0;
    };