Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/274.html
Given an array of integers citations
where citations[i]
is the number of citations a researcher received for their ith
paper, 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.
Example 1:
Input: citations = [3,0,6,1,5] Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 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,3,1] Output: 1
Constraints:
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
Algorithm
- Sort all SCI papers published by him in descending order of the number of citations;
- Search the sorted list from front to back until the serial number of a paper is greater than the number of times the paper has been cited.
The obtained serial number minus one is the H index
Code
-
public class H_Index { class Solution { public int hIndex(int[] citations) { if (citations == null || citations.length == 0) { return 0; } // @note Arrays.sort(citations); // 6,5,3,1,0 for (int i = 0; i < citations.length / 2; ++i) { int temp = citations[i]; citations[i] = citations[citations.length - i - 1]; citations[citations.length - i - 1] = temp; } for (int i = 0; i < citations.length; ++i) { if (citations[i] <= i) { // @note: <i then return i+1 will not work return i; } } return citations.length; } } } ############ class Solution { public int hIndex(int[] citations) { int n = citations.length; int[] cnt = new int[n + 1]; for (int c : citations) { if (c <= n) { ++cnt[c]; } else { ++cnt[n]; } } int sum = 0; for (int i = n; i >= 0; --i) { sum += cnt[i]; if (sum >= i) { return i; } } return 0; } }
-
// OJ: https://leetcode.com/problems/h-index/ // Time: O(NlogN) // Space: O(1) class Solution { public: int hIndex(vector<int>& A) { sort(begin(A), end(A)); int L = 0, R = A.size() - 1, N = A.size(); while (L <= R) { int M = (L + R) / 2; if (A[M] < N - M) L = M + 1; else R = M - 1; } return N - L; } };
-
class Solution: def hIndex(self, citations: List[int]) -> int: n = len(citations) cnt = [0] * (n + 1) for c in citations: if c <= n: cnt[c] += 1 else: cnt[n] += 1 sum = 0 for i in range(n, -1, -1): sum += cnt[i] if sum >= i: return i return 0 ############ class Solution(object): def hIndex(self, citations): """ :type citations: List[int] :rtype: int """ n = len(citations) dp = [0] * (n + 1) for c in citations: if c > n: dp[n] += 1 else: dp[c] += 1 total = 0 for i in reversed(range(1, len(dp))): total += dp[i] if total >= i: return i return 0
-
func hIndex(citations []int) int { n := len(citations) left, right := 0, n for left+1 < right { mid := int(uint(left+right) >> 1) if check(citations, mid) { left = mid } else { right = mid } } if check(citations, right) { return right } return left } func check(citations []int, mid int) bool { cnt := 0 for _, citation := range citations { if citation >= mid { cnt++ } } return cnt >= mid }
-
function hIndex(citations: number[]): number { let n = citations.length; let cnt = new Array(n + 1).fill(0); for (let c of citations) { if (c <= n) { ++cnt[c]; } else { ++cnt[n]; } } let sum = 0; for (let i = n; i > -1; --i) { sum += cnt[i]; if (sum >= i) { return i; } } return 0; }
-
impl Solution { #[allow(dead_code)] pub fn h_index(citations: Vec<i32>) -> i32 { let mut citations = citations; citations.sort_by(|&lhs, &rhs| { rhs.cmp(&lhs) }); let n = citations.len(); for i in (1..=n).rev() { if citations[i - 1] >= i as i32 { return i as i32; } } 0 } }