首页 > 代码库 > 274. H-Index
274. H-Index
不定期更新leetcode解题java答案。
采用pick one的方式选择题目。
题意为给定数组为每篇论文被引用次数，要求找出一个值，满足论文被引用次数不小于这个值的篇数不小于这个值。
思路为，将数组排序，从后向前循环，即可获得超过某一篇文章被引用次数的篇数，再与该文章被引用篇数进行比较，出现该文章被引用篇数小于“超过该文章被引用篇数文章的数量”，则返回上一个结果即可。
代码如下：
1 public class Solution { 2 public int hIndex(int[] citations) { 3 Arrays.sort(citations); 4 int result = 0; 5 for(int i = 1; i <= citations.length; i++){ 6 if(citations[citations.length - i] >= i) 7 result = i; 8 else 9 break;10 }11 return result;12 }13 }
上述方法应用了函数库Arrays中的排序函数sort()。在尽量节省这个步骤，可以采用另一种思路进行解题：
构建一个（最大值+1）长度的数组，数组对应储存的值为论文被引用为该数目的篇数。由此进行统计，从前向后只要满足“总数-该数组位置（被引用次数）前的篇数=大于等于该篇数的论文数目>=该位置的值（被引用次数）”即可。
代码如下：
1 public class Solution { 2 public int hIndex(int[] citations) { 3 int max = 0; 4 for(int i = 0; i < citations.length; i++) 5 if(citations[i] > max) 6 max = citations[i]; 7 int[] count = new int[max + 1]; 8 9 for(int i = 0; i < citations.length; i++)10 count[citations[i]]++;11 12 int result = 0;13 int total = 0;14 for(int i = 0; i <= max; i++){15 if(citations.length - total >= i){16 result = i;17 total += count[i];18 }else19 break;20 }21 22 return result;23 }24 }
由于这种方式节省了排序步骤，时间复杂度上较前者更低。虽然max可能很大，但是由于论文数（citations.length）是固定值，所以即使进行从0~max的循环也没有用很长的时间。
274. H-Index
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。