H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index

hifhof his/herNpapers haveat leasthcitations each, and the otherN − hpapers haveno more thanhcitations each.”For example, given

`citations = [3, 0, 6, 1, 5]`

, which 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 withat least`3`

citations each and the remaining two withno more than`3`

citations each, his h-index is`3`

.

Note: If there are several possible values for`h`

, the maximum one is taken as the h-index.

Bucket sort

class Solution { public: int hIndex(vector<int>& citations) { int n = citations.size(); int dp[n + 1]; memset(dp, 0, sizeof(dp)); for(int i = 0; i < n; i++){ if(citations[i] > n){ dp[n]++; }else{ dp[citations[i]]++; } } int total = 0; for(int i = n; i >= 0; i--){ total += dp[i]; if(total >= i){ return i; } } } };

o(nlogn) approach

class Solution { public: int hIndex(vector<int>& citations) { int ans = 0; if(citations.size() == 0) return 0; sort(citations.begin(), citations.end()); for(int i = citations.size() - 1; i >= 0; i--){ int v = citations[i]; if(v <= citations.size() - i - 1){ return citations.size() - i - 1; } } return citations.size(); } };