給一個升序排列的非零非負的整數數列 citations ， citations[i] 代表第 i 篇論文的引文次數。
找出一個 H-Index 代表至少有 n 篇被引用 n 次，要取最大值回傳。
這是一個 Rank 的排序與篩選，可以想像從 1 開始，如果有 1 篇大於 1 次就往下進行，換成看 2 。
因為是數目也是條件，所以加上計數，如果慢慢往上加到當 citations[i] > n – i 時，那就代表不合格。
題目有提示用 O(logN) Time 解決，有個經典的方式是這樣的時間複雜度：二分搜查法。
二分搜查法要切在左方合格，右方不合格的位置，最後選擇右界。
那 H-Index 是 citations[r] 嗎？不是。
在右界與之後都是 >= citations[r] 的，也就是有 n – r 篇，H-Index 的 n 篇 n 次，若有不同，也只能取 n – r 和 citations[r] 小的為主，這樣子的 H-Index 才能合要求。
不過二者的大小關係是 citations[r] >= n – r ，然後要取小為主所以 H-Index 為 n – r。
Python
class Solution:
def hIndex(self, citations: List[int]) -> int:
if not citations: return 0
n = len(citations)
l, r = 0, n
while l < r:
m = (r-l)//2 + l
if citations[m] >= n-m:
r = m
else:
l = m + 1
return n-r
C#
public class Solution {
public int HIndex(int[] citations) {
int l = 0;
int r = citations.Length;
while(l < r)
{
int m = (r-l)/2 + l;
if(citations[m] >= citations.Length - m)
r = m;
else
l = m + 1;
}
return citations.Length - r;
}
}
testcase
[100]
[]
[1]
[0,1,3,5,6]
[0,1,2,5,6]