Sponsored
Sponsored
This approach uses sorting to calculate the h-index. The idea is to sort the array of citations in descending order. Then, find the maximum number h such that there are h papers with at least h citations. This can be efficiently determined by iterating over the sorted array.
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) since the sorting is in place.
1import java.util.Arrays;
2
3public class HIndex {
4 public static int hIndex(int[] citations) {
5 Arrays.sort(citations);
6 int n = citations.length;
7 for (int i = 0; i < n; i++) {
8 if (citations[n - i - 1] < i + 1) {
9 return i;
10 }
11 }
12 return n;
13 }
14
15 public static void main(String[] args) {
16 int[] citations = {3, 0, 6, 1, 5};
17 System.out.println("H-Index: " + hIndex(citations));
18 }
19}The Java code sorts the array in ascending order and iterates in reverse to find the h-index, maintaining an overall logic similar to that of C and C++.
Given the constraints where citation counts do not exceed 1000 and the number of papers is at most 5000, a counting sort or bucket sort can be used. This approach involves creating a frequency array to count citations. Then traverse the frequency array to compute the h-index efficiently.
Time Complexity: O(n + m) where n is citationsSize and m is the maximum citation value, Space Complexity: O(m).
1#include <vector>
#include <iostream>
using namespace std;
int hIndex(vector<int>& citations) {
int n = citations.size();
vector<int> count(n + 1, 0);
for (int c : citations) {
if (c >= n) count[n]++;
else count[c]++;
}
int total = 0;
for (int i = n; i >= 0; i--) {
total += count[i];
if (total >= i) return i;
}
return 0;
}
int main() {
vector<int> citations = {3, 0, 6, 1, 5};
cout << "H-Index: " << hIndex(citations) << endl;
return 0;
}This C++ solution employs a vector to create a counting array, tracking citation frequencies.