Chỉ số H-II (H-Index II) trong C++

Mô tả bài toán

Cho mảng citations đã sắp xếp không giảm. Tính chỉ số h: lớn nhất h sao cho có ít nhất h bài báo được trích dẫn ≥ h lần.

Ví dụ: [0,1,4,5,6] → h=3 (3 bài ≥3 trích dẫn: 4,5,6).

Giải thuật Tìm kiếm nhị phân O(log n)

Vì mảng đã sắp xếp, dùng binary search tìm vị trí nhỏ nhất i sao cho citations[i] >= n - i. Khi đó h = n - i.

Chi tiết: low=0, high=n-1. mid = (low+high)/2.

• Nếu citations[mid] >= n - mid: có thể là đáp án, thu hẹp high = mid - 1.
• Ngược lại: low = mid + 1.

Cài đặt C++

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

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

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

Độ phức tạp

• Thời gian: O(log n).
• Không gian: O(1).