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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)b - *(int*)a);
6}
7
8int hIndex(int* citations, int citationsSize) {
9 qsort(citations, citationsSize, sizeof(int), compare);
10 for (int i = 0; i < citationsSize; i++) {
11 if (citations[i] < i + 1) {
12 return i;
13 }
14 }
15 return citationsSize;
16}
17
18int main() {
19 int citations[] = {3, 0, 6, 1, 5};
20 int size = sizeof(citations) / sizeof(citations[0]);
21 printf("H-Index: %d\n", hIndex(citations, size));
22 return 0;
23}The code sorts the array in descending order, then iterates through it to find the largest h such that citations[h] >= h. If no such h is found, it returns the size of the array.
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).
1def hIndex
Python's implementation features a list to serve as the frequency counter, leveraging the range of possible citation values.