H-Index II – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an array of integers citations
where citations[i]
is the number of citations a researcher received for their ith
paper and citations
is sorted in an ascending order, return compute the researcher’s h
-index.
According to the definition of h-index on Wikipedia: A scientist has an index h
if h
of their n
papers have at least h
citations each, and the other n − h
papers have no more than h
citations each.
If there are several possible values for h
, the maximum one is taken as the h
-index.
You must write an algorithm that runs in logarithmic time.
Example 1:
Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
Example 2:
Input: citations = [1,2,100] Output: 2
Constraints:
n == citations.length
1 <= n <= 105
0 <= citations[i] <= 1000
citations
is sorted in ascending order.
C++ H-Index II LeetCode Solution
int hIndex(vector<int>& c) {
int n = c.size();
if(!n) return 0;
for(int i=0;i<n;i++){
if(c[i] >= n-i) return n-i; // The first element whose value is more than the length of remaining array.
//So we return the remaining length which is the answer.
// eg [0,1,3,4,6] c[2] = 3 >2(length of remaing array) so n-i = length of remaining array + that element
}
return 0;
}
Java H-Index II LeetCode Solution
public int hIndex(int[] citations) {
int len = citations.length;
int lo = 0, hi = len - 1;
while (lo <= hi) {
int med = (hi + lo) / 2;
if (citations[med] == len - med) {
return len - med;
} else if (citations[med] < len - med) {
lo = med + 1;
} else {
//(citations[med] > len-med), med qualified as a hIndex,
// but we have to continue to search for a higher one.
hi = med - 1;
}
}
return len - lo;
}
Python 3 H-Index II LeetCode Solution
class Solution:
def hIndex(self, citations):
if not citations: return 0
n = len(citations)
beg, end = 0, n - 1
while beg <= end:
mid = (beg + end)//2
if mid + citations[mid] >= n:
end = mid - 1
else:
beg = mid + 1
return n - beg
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below