题目描述

输入是数组citations(引用的英文)输出是h指数。

citations的长度n代表总共发表的论文篇数下标代表论文名元素值代表论文被引用的次数。

h指数的意思为citations中有h篇论文被引用次数超过了h次。

如示例2中h取1至少发表了一篇论文引用次数超过1h指数为1。

h取2至少发表了2篇论文引用次数超过2不成立。

h取3至少发表了3篇论文引用次数超过3不成立。

暴力求法是先计算citations长度n然后每个元素去和n比大小都大于则输出n否则接着和nn-1比大小以此类推。

平均时间复杂度为O(n!)。

算法原理及代码实现

在暴力求法的基础上我们先对citations排序变成一个有序数组。

假如是升序排序一次循环从后向前遍历。

1次就是0至少大于h次就是h。

因此初始化h0。

citations[i]和h比大小如果citations[i]大于hh反之不执行任何操作。

最后输出h即可。

平均时间复杂度为O(n

​sort(citations.begin(),citations.end());

​for(int

in-1;i0;i--){if(citations[i]h){h;}}

​return

从3.1可以看到平均时间复杂度和排序算法的时间复杂度相同。

我们可以牺牲空间换时间使用计数排序进一步降低时间复杂度。

新建一个计数数组counter将citations中论文引用次数映射到counter中。

映射规则如下如果元素值大于ncounter[n]反之对应引用次数的下标位置citations[i]计数数组counter[citations[i]]。

C代码实现如下

i0;in;i){if(citations[i]n){counter[n];}else{counter[citations[i]];}}

​for(int

in;i0;i--){hcounter[i];//引用至少h次的论文总数if(hi){//这里的i代表引用次数return

i;}}

设左边界为left右边界为right中点为mid。

我们可以把原问题拆分成若干个子问题判断至少有mid数大于mid。

如果在区间[mid,right]满足说明搜寻的h在右边反之在左边。

平均时间复杂度O(n