H-Index ใน C++

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

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

ขั้นตอนการแก้ปัญหา (Counting Sort / Bucket)

1. n = citations.size(), สร้าง bucket[n+1]
2. นับความถี่: citation >= n → bucket[n]++, มิฉะนั้น bucket[citation]++
3. สะสมจากหลัง: cnt += bucket[i] สำหรับ i = n..0
4. เมื่อ cnt >= i → คืน i (พบ h-index)

ซับซ้อน O(N) เนื่องจาก h-index ≤ N

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

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

class Solution {
public:
    int hIndex(vector<int>& c) {
        int n = c.size();
        vector<int> bucket(n + 1);
        for (int x : c) {
            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 = {3,0,6,1,7};
    cout << ob.hIndex(v);
}

Input

[3,0,6,1,7]

Output

3