h文章

H指数计算

H指数定义:

H指数是⽤来综合衡量学者发表论⽂的数量和质量的指标。

若某学者共发表N篇论⽂,H指数是指存在h篇论⽂⾄少每篇有h引⽤量,剩下的N-h篇中，每篇都不超过h引⽤量。

⼀.排序法

复杂度

时间O(NlogN)空间O(1)

思路

先将数组排序，我们就可以知道对于某个引⽤数，有多少⽂献的引⽤数⼤于这个数。对于引⽤数citations[i]，⼤于该引⽤数⽂献的数量是

-i，⽽当前的H-Index则是(citations[i],-i)，我们将这个当前的H指数和全局最⼤的H指数来

⽐较，得到最⼤H指数。

代码

⼆.数组映射法

复杂度

时间O(N)空间O(N)

思路

也可以不对数组排序，我们额外使⽤⼀个⼤⼩为N+1的数组stats。stats[i]表⽰有多少⽂章被引⽤了i次，这⾥如果⼀篇⽂章引⽤⼤于N次，

我们就将其当为N次，因为H指数不会超过⽂章的总数。为了构建这个数组，我们需要先将整个⽂献引⽤数组遍历⼀遍，对相应的格⼦加

⼀。统计完后，我们从N向1开始遍历这个统计数组。如果遍历到某⼀个引⽤次数时，⼤于或等于该引⽤次数的⽂章数量，⼤于引⽤次数本

⾝时，我们可以认为这是H指数。之所以不⽤再向下找，因为我们要取最⼤的H指数。那如何求⼤于或等于某个引⽤次数的⽂章数量呢？我

们可以⽤⼀个变量，从⾼引⽤次的⽂章数累加下来。因为我们知道，如果有x篇⽂章的引⽤⼤于等于3次，那引⽤⼤于等于2次的⽂章数量⼀

定是x加上引⽤次数等于2次的⽂章数量。

代码

publicclassSolution{

publicinthIndex(int[]citations){

//排序

(citations);

inth=0;

for(inti=0;i<;i++){

//得到当前的H指数

intcurrH=(citations[i],-i);

if(currH>h){

h=currH;

}

}

returnh;

}

}

三.⼆分搜索法(优化)

复杂度

时间O(logN)空间O(1)

思路

在升序的引⽤数数组中，假设数组长为N，下标为i，则N-i就是引⽤次数⼤于等于下标为i的⽂献所对应的引⽤次数的⽂章数。如果该位置的

引⽤数⼩于⽂章数，则说明则是有效的H指数，如果⼀个数是H指数，那最⼤的H指数⼀定在它的后⾯（因为是升序的）。根据这点就可已

进⾏⼆分搜索了。这⾥min=mid+1的条件是citations[mid]

代码

publicclassSolution{

publicinthIndex(int[]citations){

int[]stats=newint[+1];

intn=;

//统计各个引⽤次数对应多少篇⽂章

for(inti=0;i

stats[citations[i]<=n?citations[i]:n]+=1;

}

intsum=0;

//找出最⼤的H指数

for(inti=n;i>0;i--){

//引⽤⼤于等于i次的⽂章数量，等于引⽤⼤于等于i+1次的⽂章数量，加上引⽤等于i次的⽂章数量

sum+=stats[i];

//如果引⽤⼤于等于i次的⽂章数量，⼤于引⽤次数i，说明是H指数

if(sum>=i){

returni;

}

}

return0;

}

}

publicclassSolution{

publicinthIndex(int[]citations){

intn=;

if(n==0)return0;

intmin=0,max=-1;

while(min<=max){

intmid=(min+max)/2;

//如果该点是有效的H指数，则最⼤H指数⼀定在右边

if(citations[mid]

min=mid+1;

//否则最⼤H指数在左边

}el{

max=mid-1;

}

}

//n-min是min点的H指数

returnn-min;

}

}