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 <iostream>
2#include <vector>
3
4int hIndex(std::vector<int>& citations) {
5 int n = citations.size();
6 int left = 0, right = n - 1;
7 while (left <= right) {
8 int mid = left + (right - left) / 2;
9 if (citations[mid] == n - mid) {
10 return n - mid;
11 } else if (citations[mid] < n - mid) {
12 left = mid + 1;
13 } else {
14 right = mid - 1;
15 }
16 }
17 return n - left;
18}
19
20int main() {
21 std::vector<int> citations = {0, 1, 3, 5, 6};
22 std::cout << hIndex(citations) << std::endl; // Output: 3
23 return 0;
24}The C++ implementation uses the standard library's vector to handle the citations and performs binary search, similar to the C solution, to find the h-index efficiently.
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).
1using System;
2
public class Solution {
public int HIndex(int[] citations) {
int n = citations.Length;
for (int i = 0; i < n; ++i) {
if (citations[i] >= n - i) {
return n - i;
}
}
return 0;
}
public static void Main() {
Solution sol = new Solution();
int[] citations = {0, 1, 3, 5, 6};
Console.WriteLine(sol.HIndex(citations)); // Output: 3
}
}The C# solution uses a for loop to iterate over the citations array. The approach calculates the h-index by directly verifying each citation against the required values.