สมมติว่าเรามีข้อมูลอ้างอิงของผู้วิจัยจำนวนหนึ่ง เราต้องกำหนดฟังก์ชันเพื่อคำนวณดัชนี h ของผู้วิจัย ดังที่เราทราบดัชนี h เป็นตัวชี้วัดที่ใช้ในการคำนวณผลกระทบของเอกสารของนักวิจัย ดัชนี H อย่างเป็นทางการสามารถกำหนดได้ดังนี้:"นักวิจัยมีดัชนี h ถ้า h ของเอกสาร N ของพวกเขามีการอ้างอิงอย่างน้อย h รายการและเอกสาร N h อื่น ๆ มีการอ้างอิงไม่เกิน h การอ้างอิงแต่ละรายการ"
ดังนั้น หากอินพุตเหมือนกับการอ้างอิง =[5, 4, 1, 2, 6] ผลลัพธ์จะเป็น 3 เนื่องจากเอกสารอย่างน้อย 3 รายการมีการอ้างอิงอย่างน้อย 3 รายการ − 4, 5, 6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของอาร์เรย์ สร้างหนึ่งอาร์เรย์ที่เรียกว่า bucket ขนาด n + 1
- สำหรับ i ในช่วง 0 ถึง n – 1
- x :=c[i]
- ถ้า x>=n ให้เพิ่มที่เก็บข้อมูล[n] ขึ้น 1 ไม่เช่นนั้น ให้เพิ่มที่เก็บข้อมูล[x] 1
- cnt :=0
- สำหรับฉันอยู่ในช่วง n ลงไปที่ 0:
- เพิ่ม cnt โดยที่ฝากข้อมูล[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
