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).
1using System;
2
3public class Solution {
4 public int HIndex(int[] citations) {
5 int n = citations.Length;
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 public static void Main() {
20 Solution sol = new Solution();
21 int[] citations = {0, 1, 3, 5, 6};
22 Console.WriteLine(sol.HIndex(citations)); // Output: 3
23 }
24}The C# solution performs the binary search within the method HIndex. This method efficiently narrows down the possible h-index through comparative checking using the middle index element.
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 <iostream>
2#include <vector>
int hIndex(std::vector<int>& citations) {
int n = citations.size();
for (int i = 0; i < n; ++i) {
if (citations[i] >= n - i) {
return n - i;
}
}
return 0;
}
int main() {
std::vector<int> citations = {0, 1, 3, 5, 6};
std::cout << hIndex(citations) << std::endl; // Output: 3
return 0;
}The C++ solution uses a for loop for a linear scan through the citations list. It checks if the current citation is high enough compared with the number of papers and calculates the h-index directly.