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).
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.