Leetcode題解 Python & C#：六月挑戰DAY18 H-Index II

給一個升序排列的非零非負的整數數列 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]