1.题目介绍

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数是指他（她）至少发表了 h 篇论文，并且每篇论文至少被引用 h 次。如果 h 有多种可能的值，h 指数是其中最大的那个。

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

示例 2：
输入：citations = [1,3,1]
输出：1

提示：
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

2.题解

我们就将这个问题转化一下：找到满足共有h个citations[i] > h的最大h值
这里有一个关键问题，这里有两个变量h和i，能否找到这两个变量之间的关系是解决问题的关键

2.1 贪心算法（排序）

思路

这里我们正常的思路是不是设置 h = 0,然后每找到一个citations[i] > h的数就令h++?
但是这里有一个问题，我可能在h=0的时候，citations[n] >= 0，但是当h++之后呢？就不一定了，之前能满足的条件现在不能满足，这里就是因为同时存在两个变量i和h导致的连续性问题。

那我们先将数组按从大到小的顺序进行排序呢？
根据传递性，若有citations[n] >= h，那么citations[0]>=citations[1]>=...>=citations[n] >= h,所以这里是没有问题的。

代码

1.使用新变量h

这里注意第一个数比较的对象应该是h=1，所以使用++h；最后退出的h是不满足条件的第一个h，而满足的最大h为h-1.

class Solution {
public:
    int hIndex(vector<int>& citations) {
        std::sort(citations.begin(), citations.end(), [](int a, int b) {
            return a > b;
        });
        int h = 0;
        for (auto num:citations) 
            if (num < ++h) break;
        return h-1;
    }
};

2.使用下标代替h

我们在实际上观察发现，有一个变量和h一样也是不断自加的，而且比h更好用（不用），那就是数组的下标。
但是这里由于这里下标h从0开始，然后我们第一个数比较的应该是h+1 = 1，所以这里我们使用 >h,而不是 >=h

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

复杂度分析

时间复杂度：\(O(n \log n)\)，其中 n 为数组 \(\textit{citations}\) 的长度。即为排序的时间复杂度。
空间复杂度：\(O(\log n)\)，其中 n 为数组 \(\textit{citations}\) 的长度。即为排序的空间复杂度。

2.2 计数排序

思路

根据上述解法我们发现，最终的时间复杂度与排序算法的时间复杂度有关，所以我们可以使用计数排序算法，新建并维护一个数组 counter 用来记录当前引用次数的论文有几篇。

根据定义，我们可以发现 H 指数不可能大于总的论文发表数，所以对于引用次数超过论文发表数的情况，我们可以将其按照总的论文发表数来计算即可。这样我们可以限制参与排序的数的大小为 [0,n]（其中 n 为总的论文发表数），使得计数排序的时间复杂度降低到 O(n)。

最后我们可以从后向前遍历数组 counter，对于每个 0≤i≤n，在数组 counter 中得到大于或等于当前引用次数 i 的总论文数。当我们找到一个 H 指数时跳出循环，并返回结果。

这里count数组记录的是引用次数为i的论文有几篇，这里的i既表示引用次数为i的有count[i]篇，且目前找到的是引用次数为i次的论文；题目至少发表的论文数目前为res，要求每篇论文至少被引用res次，若第一次出现 res >= i 也就是现在找到的论文引用次数小于要求每篇论文至少的引用次数，已经不满足要求，故退出循环并返回i。

这里为什么是res >= i呢？因为有这样的一种可能，我现在正处于边界值（res == i-1），再来一篇这样的论文，就有res == i了，但目前引用次数为i的论文有两篇及以上，res += count[i];的话就有res > i了，但是如果我只取其中任意一篇出来，是的 res == i,还是满足至少发表了 i 篇论文，并且每篇论文至少被引用 i 次的条件的。之后无论我只取count[i]中的几篇都是res(新)>res(旧)>i(旧)>i--（新）就肯定是不满足的情况，

代码

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        vector<int> count(n+1);
        for (int num:citations) count[min(n,num)]++;
        int res = 0;
        for (int i = n; i >= 0; i--){
            res += count[i];
            if (res >= i) return i;
        }
        return -1; //never
    }
};

2.3 二分搜索

二分搜索的思路是把我们要找的满足至少发表了 h 篇论文，并且每篇论文至少被引用 h 次的h值作为二分搜索的对象，比如像正常我们的思路是像上方那样从n（总论文数）开始一点点向下寻找h值，这里我们就直接从\(\frac{n}{2}\)开始寻找，满足就在右区间进行寻找，不满足就在左区间进行寻找，直到左右指针重合或错开。

代码

1. while (left < right){}

这里使用

2. mid = (left+right+1)>>1;为何要加1?

为防止循环卡死，若使用 mid = (left+right)>>1，考虑如下情况：

当 left 和 right 都为 0 时，mid 计算为 mid=(0+0)>>1，结果为 0。
如果此时 cnt 也为 0，那么根据条件，应该将 right 更新为 mid - 1，即 right 为 -1，这将导致循环无法终止。

3.left = mid + 1; / right = mid - 1;

class Solution {
public:
    int hIndex(vector<int>& citations) {
	    //实际h值可为0和n（citations.size()）之间的任意值
        int left = 0, right = citations.size();
        int mid = 0, cnt = 0;
        while (left < right){
	//将区域中间值作为至少引用论文值，这里+1确保mid总是向上取整，防止出现死循环
            mid = (left+right+1)>>1;
            cnt = 0;
            for (int i = 0; i < citations.size(); i++){
                // 寻找大于mid的论文数量cnt
                if (citations[i] > mid){
                    cnt++;
                }
            }
            // 如果找到的论文数量大于至少引用数，说明可行，mid实际值在右区间
            if (cnt > mid) left = mid + 1;
			//否则mid应该在左区间
            else right = mid - 1;
        }
        return cnt;
    }
};