Sponsored
Sponsored
Given the array is sorted, we can efficiently search for the h-index using binary search, aiming for logarithmic time complexity. The idea is to use the binary search to find the maximum h such that citations[h] ≥ h.
Time Complexity: O(log n).
Space Complexity: O(1).
1#include <stdio.h>
2
3int hIndex(int* citations, int citationsSize) {
4 int left = 0, right = citationsSize - 1, n = citationsSize;
5 while (left <= right) {
6 int mid = left + (right - left) / 2;
7 if (citations[mid] == n - mid) {
8 return n - mid;
9 } else if (citations[mid] < n - mid) {
10 left = mid + 1;
11 } else {
12 right = mid - 1;
13 }
14 }
15 return n - left;
16}
17
18int main() {
19 int citations[] = {0, 1, 3, 5, 6};
20 int n = sizeof(citations) / sizeof(citations[0]);
21 printf("%d\n", hIndex(citations, n)); // Output: 3
22 return 0;
23}The C solution defines a function hIndex using binary search to find the h-index. It utilizes a loop to adjust left and right boundaries based on comparison, reducing the search space logarithmically.
In this linear scan approach, we traverse the sorted citations list from beginning to end. The goal is to determine the maximum valid h-index by checking citations against their corresponding paper count.
Time Complexity: O(n).
Space Complexity: O(1).
1#include
This C implementation uses a simple loop to check each citation's sufficiency against its position in the list, returning the calculated h-index when the condition is satisfied.