Sorting is a natural solution. But, you don‘t have to run O(nlgn) sorting for all the time. Counting sort is O(n)!
class Solution { public: int hIndex(vector<int>& cit) { int len = cit.size(); vector<long> hist(cit.size()+1,0); for(int i=0;i<len;++i) hist[min<int>(len,cit[i])]++; long cumSum=0; for(int i=len;i>=0;--i) { cumSum+=hist[i]; if(cumSum>=i) return i; } return 0; } };
原文：http://www.cnblogs.com/tonix/p/4781184.html