H-Index - Chỉ số H từ danh sách trích dẫn

Cho mảng trích dẫn của một nhà nghiên cứu. Tính chỉ số h-index: số lớn nhất h sao cho có ít nhất h bài báo mỗi bài có ≥ h trích dẫn, và các bài còn lại ≤ h trích dẫn.

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

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

Tạo mảng bucket kích thước n+1. bucket[i] = số bài có đúng i trích dẫn (với i >= n gom vào bucket[n]). Duyệt từ n xuống 0, cộng dồn cnt. Khi cnt >= i trả về i.

Cài đặt C++

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

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

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

Đầu vào

[5, 4, 1, 2, 6]

Đầu ra

3