leetcode [275]H-Index II

佚名 7年前 (2019-05-13) 随笔 1254人围观抢沙发百度已收录

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example:

Input: citations = [0,1,3,5,6]
Output: 3 
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had 
             received 0, 1, 3, 5, 6 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note:

If there are several possible values for h, the maximum one is taken as the h-index.

Follow up:

This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
Could you solve it in logarithmic time complexity?

题目大意：

这一题和leetcode[274]是一样的套路，只是给定的citation数组是已经排好顺序的。

解法：

　　这一道题目可以按照上一题桶排序的思想做，时间复杂度为O(n)。而这道题目的follow up中有提到希望能在对数级别的时间复杂度解决问题。很明显就能想到二分查找，二分查找有以下的情况：

　　1:引文[mid] == leni -mid，那么这意味着有[mid]论文至少有引文[mid]。

　　2:引文[mid] > leni -mid，这意味着有文献[mid]的引文量大于文献[mid]的引文量，所以我们应该继续在左半部分搜索

　　3:引文[mid] < leni -mid，我们应该继续在右侧搜索

　　迭代之后，我们保证right+1是我们需要找到的(即len-(right+1) papars至少有len-(righ+1)引用)

java：

class Solution {
    public int hIndex(int[] citations) {
        int len=citations.length,left=0,right=len-1;
        while(left<=right){
            int mid=(left+right)>>1;
            if (citations[mid]==(len-mid)) return citations[mid];
            else  if (citations[mid]>(len-mid)) right=mid-1;
            else left=mid+1;
        }

        return len-(right+1);
    }
}