<Array> 274 275

274. H-Index

这道题让我们求H指数，这个质数是用来衡量研究人员的学术水平的质数，定义为一个人的学术文章有n篇分别被引用了n次，那么H指数就是n.

用桶排序，按引用数从后往前计算论文数量，当论文数 >= 当前引用下标时。满足至少有N篇论文分别被引用了n次。

class Solution {

    public int hIndex(int[] citations) {

        int n = citations.length;

        int[] bucket = new int[n + 1];

        for(int c : citations){

            if(c >= n){

                bucket[n]++;

            }else{

                bucket[c]++;

            }

        }

        int count = 0;

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

            count += bucket[i];

            if(count >= i){

                return i;

            }

        }

        return 0;

    }

}

275. H-Index II

有len - mid篇文章，每篇文章至少有 citations[ mid ] 次引用。

1. len - mid == citations[ mid ], 符合

2. len - mid > citations[ mid ] , 文章数》引用次数，不符合定义，往右搜索

3. len - mid < citations[ mid ], 文章数《引用次数，符合定义，但说明可能有更多的文章每篇被引用citations[ mid ] 次，往左搜索。

len - (right + 1 ) = 总文章数 - 不符合定义的文章数。

class Solution {

    public int hIndex(int[] citations) {

        int len = citations.length;

        int left = 0, right = len - 1;

        while(left <= right){

            int mid = left + (right - left) / 2;

            if(len - mid == citations[mid]){

                return citations[mid];

            } else if( len - mid > citations[mid]){

                left = mid + 1;

            }else{

                right = mid - 1;

            }

        }

        return len - (right + 1);

    }

}

巴特西

<Array> 274 275

最新文章

热门文章