題目連結:
題目意譯:
給定一整數陣列 citations,其中 citations[i] 為一位研究人員的第 i 篇論文之被引用數量,而且 citations 以升序之順序排序。計算並回傳該研究人員的 H 指數(H-index)。
根據維基百科上的
H 指數之定義:一位科學家如果有著 n 篇論文,而其中有 h 篇論文各自至少有著 h 次的引用次數且剩下 n - h 篇各自有著不超過 h 次的引用次數,則他的 H 指數即為 h。
如果有多個可能的 h 值,當中最大者將視為 H 指數。
你必須寫出一個可以在對數時間內求得解的演算法。
限制:
n == citations.length
1 ≦ n ≦ 10 ^ 5
0 ≦ citations[i] ≦ 1000
citations 以升序之順序排序。
範例測資:
範例 1:
輸入: citations = [0,1,3,5,6]
輸出: 3
解釋: [0,1,3,5,6] 代表著研究人員總共有 5 篇論文,而各自被引用了 0 、 1 、 3 、 5 、 6 次的引用。
由於研究人員有著 3 篇論文各自至少被引用 3 次,而剩下的 2 篇則各自被引用不超過 3 次,他的 H 指數為 3。
範例 2:
輸入: citations = [1,2,100]
輸出: 2
解題思維:
跟
這題類似,對答案進行二分搜尋法(Binary Search)即可。
假設我們現在猜 H-index 為 x,而如果 n - x > citations[x],代表我們的 H-index 猜得太低了,應該猜大一點的 x 值;反之,我們可以試著猜小一點的 x 值。
最後便可以找到一個最小且合法的 H-index,即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。