leetcode

    xiaoxiao2021-03-25  279

    题意:

    一个数组,代表一个学者的所有论文。每个数值代表该篇论文的引用次数。找到一个最大的数值h,使该学者有h篇论文至少都被引用h次,其它的所有论文都至多被引用h次。。

    分析:

    看作是一个横纵坐标的直方图,只需要两重循环,从上向下(因为要找最大的)遍历搜索y轴,内循环遍历x轴判断。

    public class Solution { public int hIndex(int[] citations) { int h = citations.length; while(h>=1){ int count = 0; for(int c: citations){ if(h <= c) count++; } if(count >= h){ return h; } h--; } return h; } }但是我们可不可以继续优化呢?

    这个时候我们要优化,必然要尝试用空间换时间了。

    我们的循环能不能去掉呢?

    先想清楚我们的循环在干什么?

    外循环:遍历论文值,寻找最大的可能论文值。

    内循环:对于一个论文值,遍历所有的论文,看有多少论文的值大于等于这个值。

    我们看看有没有信息,不用去循环遍历查找,而可以存储起来的,显然最可能的信息是:有多少论文的值大于等于这个值。这个信息

    所以我们可以存储这个信息。比如5篇论文:引用数为1,2,3,4,5(大于5)的分别是多少。

    public class Solution { public int hIndex(int[] citations) { int[] message = new int[citations.length+1]; int sum = 0; for(int i=0; i<citations.length; i++){ if(citations[i] < citations.length){ message[citations[i]]++; }else{ message[citations.length]++; } } int h=citations.length; for(; h>0; h--){ sum += message[h]; if(sum >= h){ return h; } } return h; } }

    转载请注明原文地址: https://ju.6miu.com/read-329.html

    最新回复(0)