สมมติว่ามีอาร์เรย์ของอ้างอิงของนักวิจัย เราต้องกำหนดฟังก์ชันเพื่อคำนวณ h-index ของนักวิจัย ตามที่เรารู้ h-index เป็นเมตริกที่ใช้คำนวณผลกระทบของเอกสารของนักวิจัย อย่างเป็นทางการ H-index สามารถนิยามได้ว่า: "นักวิจัยมีดัชนี h ถ้ามี h ใน N เอกสารของพวกเขาที่มีอ้างอิงอย่างน้อย h ครั้งต่อเอกสาร และเอกสารอื่น N - h มีอ้างอิงไม่เกิน h ครั้งต่อเอกสาร"
เช่น ถ้าอินพุทเป็น citations = [5, 4, 1, 2, 6] ผลลัพธ์จะเป็น 3 เนื่องจากมีอย่างน้อย 3 เอกสารที่มีอ้างอิงอย่างน้อย 3 ครั้งต่อเอกสาร คือ 4, 5, 6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
- n := ขนาดของอาร์เรย์ สร้างอาร์เรย์ bucket ขนาด n + 1
- ลูป i ในช่วง 0 ถึง n-1
- x := c[i]
- ถ้า x >= n แล้ว เพิ่ม bucket[n] ขึ้น 1 มิฉะนั้นเพิ่ม bucket[x] ขึ้น 1
- cnt := 0
- ลูป i จาก n ลงมาหา 0:
- เพิ่ม cnt ด้วย bucket[i]
- ถ้า cnt >= i แล้วคืนค่า i
- คืนค่า -1
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
ตัวอย่าง
#include <bits/stdc++.h> using namespace std; class Solution { public: int solve(vector<int>& c) { int n = c.size(); vector <int> bucket(n + 1); 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; } }; main(){ Solution ob; vector<int> v = {5, 4, 1, 2, 6}; cout << (ob.solve(v)); } อินพุท
[5, 4, 1, 2, 6]
เอาต์พุท
3
