leetcode274 H指数 —— 排序后遍历/差分 c++

给你一个整数数组 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

最容易理解的——排序后遍历

先对原数组进行排序，我们要找最大值的h就是要满足大于等于h的数大于等于h，所以排序之后我们可以知道大于每个数的数有多少，进行查找最大值即可

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

    }
};

稍微优化——遍历改成二分搜索

class Solution {
public:
    int hIndex(vector<int>& citations) {
        size_t n = citations.size();
        sort(citations.begin(), citations.end());
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (citations[mid] >= n - mid) high = mid - 1;
            else low = mid + 1;
        }
        return n - low;
    }
};

差分数组解法（计数排序）

差分数组讲解可参考【算法】排序算法之计数排序 - 知乎 (zhihu.com)

这里因为h<=n,所以大于n的数按n算就行，cnt数组大小n+1

C++

class Solution {
public:
    int hIndex(vector<int>& citations) {
        //计数排序
        int n=citations.size();
        vector<int> counter(n+1) ;//因为h<=n,所以>n的值都存入counter[n]
        for(int i=0;i<n;i++) {
            if(citations[i]>=n) counter[n]++;
            else counter[citations[i]]++;
        }

        int cnt=0;//cnt记录大于i （即citations[某个值]）的值个数
        for(int i=n;i>=0;i--) {//从大到小遍历
            cnt+=counter[i];
            if(cnt>=i) {
                //如果大于i的数个数大于i，那么h=i
                return i;
            }
        }
        return 0;

    }
};

python:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n=len(citations)
        counter=[0]*(n+1)
        for i in citations:
            if i >= n :
                counter[n]+=1
            else :
                counter[i]+=1
        
        cnt=0
        for i in range(n,-1,-1) :
            cnt+=counter[i]
            if cnt>=i:
                return i
        return 0