题目描述

给定一位研究者论文被引用次数的数组(被引用次数是非负整数),数组已经按照升序排列。编写一个方法,计算出研究者的 h 指数。

h 指数的定义: “h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (N 篇论文中)至多有 h 篇论文分别被引用了至少 h 次。(其余的 N – h 篇论文每篇被引用次数不多于 次。)”

示例:

输入: citations = [0,1,3,5,6]
输出: 3 
解释: 给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
     由于研究者有 3 篇论文每篇至少被引用了 3 次,其余两篇论文每篇被引用不多于 3 次,所以她的 h 指数是 3

说明:

如果 有多有种可能的值 ,h 指数是其中最大的那个。

进阶:

  • 这是 H指数 的延伸题目,本题中的 citations 数组是保证有序的。
  • 你可以优化你的算法到对数时间复杂度吗?

https://leetcode-cn.com/problems/h-index-ii/

解法1

本题目和274. H指数的区别是,文章已经按照应用次数排序。此外,题目要求优化到对数时间复杂度,很自然能联想到Binary Search。

那么本题Search的是什么呢?我们要Search的是一个最小的mid,使得citations[mid] >= |citations| – mid,而此时hIndex = |citations| – mid。这个等式是根据hIndex的定义而来。首先”|citations| – mid”表示从mid开始到最后有几篇文章,此外要求这些文章中最低的引用数量至少等于文章数量,通过citations[mid]能取到这些文章中最低引用数量(因为以及按引用数量排序)。而最小的mid能够使得|citations| – mid最大,因为题目要求取最大的hIndex。

通过上面分析,我们不难编写出二分查找的代码。时间复杂度为O(logn),空间复杂度为O(1)。

class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        int start = 0;
        int end = len - 1;
        int res = 0;

        while (start <= end) {
            int mid = (start + end) >>> 1;
            int paperCnt = len - mid;
            // len - mid 代表从mid到len到论文数量,若想len - mid作为hIndex
            // 则要求从mid到len中最低引用的那篇论文的citations大于等于len - mid(也就是citations[mid]>=paperCnt)。
            // 若满足这个条件,我们尝试能不能让hIndex更大些,也就是mid往左一些,那么我们就调整end = mid - 1
            // 若条件不满足,我们让mid向右面移动,这样paperCnt就少了,同时citations[mid]也大了,我们再看看从mid开始到len能不能作为hIndex
            if (citations[mid] >= paperCnt) {
                res = paperCnt;
                end = mid - 1;
            } else
                start = mid + 1;
        }
        return res;
    }
}
pwrliang Algorithms, Array, Binary Search ,

Leave a Reply

Your email address will not be published. Required fields are marked *