【每日一题Day362】LC274H 指数 | 二分答案

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

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

来晚了 奔波的一天

• 思路

  • 二段性：存在最大值y使，少于等于y的数值一定满足条件；大于y的数值一定不满足条件
  • 二分答案y
    • 引用次数大于等于y的论文数目大于等于y，那么向右搜索获得更大的y
    • 引用次数大于等于y的论文数目小于y，那么向左搜索获得更大的y
  • check:排序后可以快速算出引用次数大于等于y的论文数目

• 实现

  class Solution {
      public int hIndex(int[] citations) {
          
          int n = citations.length;
          Arrays.sort(citations);
          int l = 1, r = n;
          int res = 0;
          while (l <= r){
              int mid =(l + r) >> 1;
              if (check(citations, mid) >= mid){
                  res = Math.max(res, mid);
                  l = mid + 1;            
              }else{
                   r = mid - 1;
              }
          }
          return res;
      }
      public int check(int[] citations, int target){
          int n = citations.length;
          int l = 0, r = n - 1;
          while (l <= r){
              int mid = l + r >> 1;
              if (citations[mid] < target){
                  l = mid + 1;
              }else{
                  r = mid - 1;
              }
          }
          // l为第一个符合的下标
          return n - l;// 大于等于target的引用次数的数目
  
      }
  }
  

  • 复杂度
    • 时间复杂度：$O(nlogm)$，$n$是数组的长度，m是二分查找的上界。二分查找的时间复杂度是$O(logm)$，每次判断需要的时间复杂度为$O(n)$
    • 空间复杂度：$O(\log n)$