275. H-Index II

Same as problem "274. H-Index".

1:  class Solution {  
2:  public:  
3:    int hIndex(vector<int>& citations) {  
4:      int h = 0, n = citations.size();  
5:      for (h = 0; h < n; h++) {  
6:        if (citations[h] >= n-h) break;  
7:      }  
8:      return n-h;  
9:    }  
10:  };  

274. H-Index

I was thinking of scanning from the end and choose citations[i] if citations[i] >= n-i. However it turns out wrong. For example [100], the citation should be 1 instead of 100. The right way is to scan from the beginning and choose (n-i) as citation.

1:  class Solution {  
2:  public:  
3:    int hIndex(vector<int>& citations) {  
4:      sort(citations.begin(), citations.end());  
5:      int h = 0, n = citations.size();  
6:      for (int i = 0; i < n; i++) {  
7:        if (citations[i] >= n-i) {  
8:          h = n-i;  
9:          break;  
10:        }  
11:      }  
12:      return h;  
13:    }  
14:  };  

When I revisited this problem, I found a better explanation of the algorithm. If you sort the citations and put it into a graph, where x-axis represents the paper index and y-axis represents the citations. So, from the graph, the H-Index is length of the maximum square that in the histogram.