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