LeetCode 面试经典 150_数组/字符串_H 指数（9_274_C++_中等）(排序后再进行判断)(计数)

题目描述：

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 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

题解：

解题思路：

思路一（排序后再进行判断）：

1、首先需理清题意，h 指数：至少有 h 篇论文引用个数 >=h。(若h=3 , 则至少 3 篇论文引用 >=3)。将论文的引用次数进行排序后，先从引用次数多的论文进行判断。
例：citations = [3,0,6,1,5]
① 排序： [0,1,3,5,6]
② 从引用次数多的论文进行判断，h 初始值为 0。
     6 > 0 h=1
     5 > 1 h=2
     3 > 2 h=3
     1 < 3 结束
citations[i] > h，h++。h变化后 h <= citations[i]。（citations[i] >= h）

2、复杂度分析：
① 时间复杂度：O(nlog(n))，n 为 数组中元素的个数，主要是快速排序消耗的时间。
② 空间复杂度：O(log(n))，主要是快速排序消耗的时间。

思路二（计数）：

1、创建一个数组，将论文引用的次数进行统计。
例：citations = [3,0,6,1,5]
count(6) 数组来存储 引用数量为下标 i 的论文个数（count[1]代表引用次数为 1 的论文个数，count[2]代表引用次数为 2 的论文个数）。
因此数组 h 最大为 5,将引用次数 >=5 的论文个数统一存储在 count[5]中 (count[5]代表引用次数为 >=5 的论文个数)

统计个数：0,1,2,3,4,5
      count=[1,1,0,1,0,2]
从后向前累计count中论文出现次数sum，与 count中的下标i(引用次数)进行比较。若sum >=i 则返回 i。
① i=5，sum=2，sum<5
② i=4，sum=2，sum<4
③ i=4，sum=3,sum>=3 返回 3。

2、复杂度分析
① 时间复杂度：O(n)，n 为 数组中元素的个数，需遍历一遍原数组统计个数，再遍历一遍count数组进行判断。
② 空间复杂度：O(1)。

代码实现

代码实现（思路一（排序后再进行判断 ））：

class Solution1 {
public:int hIndex(vector<int>& citations) {// 对 citations 数组进行升序排序sort(citations.begin(), citations.end());// 初始化 h 指数为 0，i 指向数组的最后一个元素int h = 0, i = citations.size() - 1;// 当 i >= 0 且 citations[i] 大于当前的 h 时，继续寻找符合条件的 H 指数while (i >= 0 && citations[i] > h) {// 每次循环，H 指数加 1h++;// i 向前移动，检查下一篇论文的引用次数i--;    }// 返回计算出的 H 指数return h;}
};

代码实现（思路二（计数））：

class Solution2 {
public:int hIndex(vector<int>& citations) {// 获取论文数量int n = citations.size();// 创建一个长度为 n+1 的数组 count，用于统计每个引用次数出现的频率vector<int> count(n + 1, 0);// 遍历 citations 数组，统计每个引用次数的频率for (const auto &i : citations) {// 对于每个引用次数 i，如果 i 大于 n，则归为 n，表示至少有 n 次引用count[min(n, i)]++;}// 初始化累计的论文数int sum = 0;// 从引用次数最多的论文开始，倒序遍历 count 数组for (int i = n; i >= 0; i--) {// 累加 count[i]，表示引用次数至少为 i 的论文数sum += count[i];// 如果累计的论文数大于或等于 i，说明找到了符合条件的 H 指数if (sum >= i) {return i;}}// 如果没有符合条件的 H 指数，返回 0return 0;}
};

以思路一为例进行调试

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;class Solution1 {
public:int hIndex(vector<int>& citations) {// 对 citations 数组进行升序排序sort(citations.begin(), citations.end());// 初始化 h 指数为 0，i 指向数组的最后一个元素int h = 0, i = citations.size() - 1;// 当 i >= 0 且 citations[i] 大于当前的 h 时，继续寻找符合条件的 H 指数while (i >= 0 && citations[i] > h) {// 每次循环，H 指数加 1h++;// i 向前移动，检查下一篇论文的引用次数i--;    }// 返回计算出的 H 指数return h;}
};int main(int argc, char const *argv[])
{vector<int> citations={1,3,1} ;Solution1 s1;cout<< s1.hIndex(citations);return 0;
}

LeetCode 面试经典 150_数组/字符串_数组/字符串_H 指数（9_274)原题链接
欢迎大家和我沟通交流(✿◠‿◠)