LeetCode 275 H-Index II：有序引用陣列的二分查找優化

題目描述

給定**已按升序排列**的引用次數陣列 citations，計算 H 指數：至少有 h 篇論文引用數 ≥ h。優化至 O(log n)。

觀察

陣列升序，索引 i 對應第 i+1 小引用數。共有 n-i 篇論文引用數 ≥ citations[i]。H 指數為最大的 h 滿足 citations[i] ≥ n-i。

二分查找

尋找最小索引 i 使 citations[i] ≥ n - i，則 h = n - i。

代碼實作

class Solution {
public:
    int hIndex(vector& citations) {
        int n = citations.size();
        if (n == 0) return 0;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (n - mid > citations[mid])  // 條件不滿足，往右找
                left = mid + 1;
            else
                right = mid;
        }
        // 迴圈結束 left == right
        return min(n - left, citations[left]);
    }
};

線性掃描備選（簡單但較慢）

int hIndex(vector& citations) {
    int n = citations.size(), h = 0;
    for (int i = n - 1; i >= 0; --i) {
        if (h >= citations[i]) return h;
        ++h;
    }
    return n;
}

複雜度

關鍵點

• 利用有序性將線性掃描降為對數查找。
• 返回 min(n-i, citations[i]) 處理邊界情況（如 [100] → h=1）。