為了方便，將 citations 記為 cs。

所謂的 h 指數(shù)是指一個(gè)具體的數(shù)值，該數(shù)值為“最大”的滿足「至少發(fā)表了 x 篇論文，且每篇論文至少被引用 x 次」定義的合法數(shù)，重點(diǎn)是“最大”。

用題面的實(shí)例 1 來舉個(gè) 🌰，給定所有論文的引用次數(shù)情況為 cs = [3,0,6,1,5]，可統(tǒng)計(jì)滿足定義的數(shù)值有哪些：

h=0，含義為「至少發(fā)表了 0 篇，且這 0 篇論文至少被引用 0 次」，空集即滿足，恒成立；

h=1，含義為「至少發(fā)表了 1 篇，且這 1 篇論文至少被引用 1 次」，可以找到這樣的組合，如 [3]，成立；

h=2，含義為「至少發(fā)表了 2 篇，且這 2 篇論文至少被引用 2 次」，可以找到這樣的組合，如 [3, 6]，成立；

h=3，含義為「至少發(fā)表了 3 篇，且這 3 篇論文至少被引用 3 次」，可以找到這樣的組合，如 [3, 6, 5]，成立；

h=4，含義為「至少發(fā)表了 4 篇，且這 4 篇論文至少被引用 4 次」，找不到這樣的組合，不成立；

...

實(shí)際上，當(dāng)遇到第一個(gè)無法滿足的數(shù)時(shí)，更大的數(shù)值就沒必要找了。一個(gè)簡(jiǎn)單的推導(dǎo)：

至少出現(xiàn) k 次的論文數(shù)不足 k 篇 => 至少出現(xiàn) k+1 次的論文必然不足 k 篇 => 至少出現(xiàn) k+1 次的論文必然不足 k+1 篇（即更大的 h 不滿足）。

二分
基于此分析，我們發(fā)現(xiàn)對(duì)于任意的 cs（論文總數(shù)量為該數(shù)組長(zhǎng)度 n），都必然對(duì)應(yīng)了一個(gè)最大的 h 值，且小于等于該 h 值的情況均滿足，大于該 h 值的均不滿足。

那么，在以最大 h 值為分割點(diǎn)的數(shù)軸上具有「二段性」，可通過「二分」求解該分割點(diǎn)（答案）。

最后考慮在什么值域范圍內(nèi)進(jìn)行二分？

一個(gè)合格的二分范圍，僅需確保答案在此范圍內(nèi)即可。

再回看我們關(guān)于 h 的定義「至少發(fā)表了 x 篇論文，且每篇論文至少被引用 x 次」，滿足條件除了引用次數(shù)，還有論文數(shù)量，而總的論文數(shù)量只有 n，因此最大的 h 只能是 n 本身，而不能是比 n 大的數(shù)，否則論文數(shù)量就不夠了。

綜上，我們只需要在 [0,n] 范圍進(jìn)行二分即可。對(duì)于任意二分值 mid，只需線性掃描 cs 即可知道其是否合法。

代碼：

int hIndex(int* citations, int citationsSize) {
int left=0,right=citationsSize;int mid=0,cnt=0;while(left<right){// +1 防止死循環(huán)mid=(left+right+1)>>1;cnt=0;for(int i=0;i<citationsSize;i++){if(citations[i]>=mid){cnt++;}}if(cnt>=mid){// 要找的答案在 [mid,right] 區(qū)間內(nèi)left=mid;}else{// 要找的答案在 [0,mid) 區(qū)間內(nèi)right=mid-1;}}return left;}

作者：宮水三葉
?

?