H-Index II ใน C++

ให้อาร์เรย์ citations เรียงจากน้อยไปมาก (non-decreasing) หา h-index: h = จำนวนสูงสุดที่มีอย่างน้อย h บทความถูกอ้างอิง ≥ h ครั้ง

ตัวอย่าง: [0,1,4,5,6] → 3 (มี 3 บทความ ≥ 3: 4,5,6)

ขั้นตอนการแก้ปัญหา (Binary Search)

1. low = 0, high = n-1
2. Binary search:
   • mid = low + (high-low)/2
   • ถ้า → คืน citations[mid]
   • ถ้า n - mid → ไปซ้าย (high = mid-1)
   • มิฉะนั้น → ไปขวา (low = mid+1)
3. คืน n - (high + 1)

เหตุผล: n - mid = จำนวนบทความจาก mid ถึงสุด ถ้า citations[mid] ≥ n-mid แสดงว่าอาจเป็น h-index ได้

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int hIndex(vector<int>& A) {
        int n = A.size();
        if (n == 0) return 0;
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (A[mid] == n - mid) return A[mid];
            else if (A[mid] > n - mid) high = mid - 1;
            else low = mid + 1;
        }
        return n - (high + 1);
    }
};

int main() {
    Solution ob;
    vector<int> v = {0,1,4,5,7};
    cout << ob.hIndex(v);
}

Input

[0,1,4,5,6]

Output

3