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

Mô tả bài toán

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

Ví dụ: [3,0,6,1,7] → h=3 (3 bài ≥3: 3,6,7).

Giải thuật Counting Sort / Bucket O(n)

Vì h-index ≤ n (số bài báo). Tạo bucket size n+1:

bucket[i] = số bài có đúng i trích dẫn (với i=n gom tất cả ≥ n).

Duyệt ngược từ n xuống 0, cộng dồn cnt. Khi → trả về i.

Cài đặt C++

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

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        vector<int> bucket(n + 1, 0);
        for (int c : citations) {
            if (c >= n) bucket[n]++;
            else bucket[c]++;
        }
        int cnt = 0;
        for (int i = n; i >= 0; i--) {
            cnt += bucket[i];
            if (cnt >= i) return i;
        }
        return 0;
    }
};

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

Độ phức tạp

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