274. H 指數

題目

給你(ni)一個整數(shu)數(shu)組 citations ，其中(zhong) citations[i] 表(biao)示研究(jiu)者的(de)第 i 篇(pian)論文(wen)被引用(yong)的(de)次數(shu)。計算并返回該研究(jiu)者的(de) h 指數(shu)。

根據(ju)維基百(bai)科(ke)上 h 指數的(de)定義：h 代表(biao)“高引(yin)用次(ci)數” ，一名科(ke)研人(ren)員的(de) h 指數 是指他（她）至(zhi)少(shao)發表(biao)了 h 篇(pian)論文(wen)，并且 至(zhi)少(shao) 有 h 篇(pian)論文(wen)被(bei)引(yin)用次(ci)數大(da)于(yu)等于(yu) h 。如果 h 有多(duo)種可能(neng)的(de)值，h 指數 是其中最大(da)的(de)那個。

示例

示例 1：

輸入：citations = [3,0,6,1,5]

輸出：3

解釋：給定數組表示研究者總共有 5 篇論文，每篇論文相應的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇論文每篇 至少(shao) 被引用了 3 次，其余(yu)兩(liang)篇論文每篇被引用 不多(duo)于 3 次，所以她的(de) h 指數(shu)是 3。

示例 2：

輸入：citations = [1,3,1]

輸出：1

解法

解法一：遍歷所有可能性

public int hIndex(int[] citations) {
     if (citations == null || citations.length <= 0)
          return 0;

     int count = 0;
     for (int h = 1; h <= citations.length; h++) {
          count = 0;
          for (int i = 0; i < citations.length; i++) {
               if (citations[i] >= h) {
               count++;
               }
          }
          if (count < h) {
               return h - 1;
          }
     }
     return count;
}

時間復雜度：O(n^2)
空間復雜度：O(1)

解法二

二分搜索

public int hIndex(int[] citations) {
     if (citations == null || citations.length <= 0)
          return 0;

     int left = 0, right = citations.length;
     int mid = 0, cnt = 0;
     while (left < right) {
          mid = (left + right + 1) >> 1;
          cnt = 0;
          for (int i = 0; i < citations.length; i++) {
               if (citations[i] >= mid) {
               cnt++;
               }
          }
          if (cnt >= mid) {
               // 要找的答案在 [mid,right] 區間內
               left = mid;
          } else {
               // 要找的答案在 [0,mid) 區間內
               right = mid - 1;
          }
     }
     return left;
}