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).
1public class Solution {
2 public int hIndex(int[] citations) {
3 int n = citations.length;
4 int left = 0, right = n - 1;
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 public static void main(String[] args) {
18 Solution sol = new Solution();
19 int[] citations = {0, 1, 3, 5, 6};
20 System.out.println(sol.hIndex(citations)); // Output: 3
21 }
22}The Java solution implements binary search within an hIndex method. The search continues until the correct h value is found, using conditions to check against the middle values of the citations array.
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.