LeetCode 274. H指数（排序，哈希）

示例:
输入: citations = [3,0,6,1,5]
输出: 3 
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，
     所以她的 h 指数是 3。

说明: 如果 h 有多种可能的值，h 指数是其中最大的那个。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), [](int &a, int &b){return a > b;});
        int i = 0;
        while(i < citations.size() && citations[i] > i)// y >= i+1
        	i++;
        return i;
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), [](int &a, int &b){return a > b;});
        //找最后一个citations[i] >= i+1
        int l = 0, r = citations.size()-1, mid;
        while(l <= r)
        {
        	mid = l + ((r-l)>>1);
        	if(citations[mid] < mid+1)
        		r = mid-1;
        	else
        	{
        		if(mid == citations.size()-1 || citations[mid+1] < mid+2)
        			return mid+1;
        		l = mid+1;
        	}
        }
        return l;
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size(), i;
        int paper[n+1] = {0};
        for(i = 0; i < n; ++i)
        	paper[min(citations[i], n)]++;//引用次数超过n的不影响结果
        	//引用次数是下标，有多少篇(值)
        int count = n;//引用n次的
        int papers = paper[n];//文章总数papers
        while(count > papers)
        {
        	count--;
        	papers += paper[count];
        }
        return count;
    }
};