Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/275.html
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 ascending order, return the researcher's h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h
such that the given researcher has published at least h
papers that have each been cited at least h
times.
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.
Algorithm
First initialize left and right to 0 and len-1, then take the middle value mid, compare citations[mid] with len-mid,
- If the former is big, right moves before mid
- On the contrary, right moves after mid
The loop condition is left<=right, and finally returns
len-left
.
Code
-
public class H_Index_II { class Solution { public int hIndex(int[] citations) { int len = citations.length, left = 0, right = len - 1; while (left <= right) { int mid = (left + right) / 2; if (citations[mid] == len - mid) { return len - mid; } else if (citations[mid] > len - mid) { // cites > h`, try next round right = mid - 1; } else { left = mid + 1; } } return len - left; } } } ############ class Solution { public int hIndex(int[] citations) { int n = citations.length; int left = 0, right = n; while (left < right) { int mid = (left + right + 1) >> 1; if (citations[n - mid] >= mid) { left = mid; } else { right = mid - 1; } } return left; } }
-
// OJ: https://leetcode.com/problems/h-index-ii/ // Time: O(logN) // Space: O(1) class Solution { public: int hIndex(vector<int>& A) { int N = A.size(), L = 0, R = N - 1; while (L <= R) { int M = (L + R) / 2; if (A[M] >= N - M) R = M - 1; else L = M + 1; } return N - L; } };
-
class Solution: def hIndex(self, citations: List[int]) -> int: n = len(citations) left, right = 0, n while left < right: mid = (left + right + 1) >> 1 if citations[n - mid] >= mid: left = mid else: right = mid - 1 return left ############ class Solution(object): def hIndex(self, citations): """ :type citations: List[int] :rtype: int """ if not citations: return 0 n = len(citations) start, end = 0, n - 1 while start < end: mid = start + (end - start) / 2 if citations[mid] >= n - mid: end = mid else: start = mid + 1 return n - start if citations[start] != 0 else 0
-
func hIndex(citations []int) int { n := len(citations) left, right := 0, n for left < right { mid := (left + right + 1) >> 1 if citations[n-mid] >= mid { left = mid } else { right = mid - 1 } } return left }
-
function hIndex(citations: number[]): number { const n = citations.length; let left = 0, right = n; while (left < right) { const mid = (left + right + 1) >> 1; if (citations[n - mid] >= mid) { left = mid; } else { right = mid - 1; } } return left; }