275. H指数 II

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

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

示例:

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

说明:

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

进阶：

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

本题看到要对数复杂度，并且是有序的，那就想到了二分算法。
算法很轻松的就想到了，但是处理本题没那么简单，因为本题的判断和返回值和普通的二分查找是不一样的。
我们设数组总数为n
当 citations[mid] == n - mid 相同的时候，我们直接返回n - mid。
否则我们就要进行判断

• 如果 citations[mid] > n - mid 就说明，该数不可能是H指数，那就说明H指数存在的话就一定在前面。
• 如果citations[mid] < n-mid 就说明，该数是H指数，但是不一定是最大H指数，我们往后查询看看。

本题我们需要返回的是n - mid 因为H指数不是一定在数组中一定存在的，而是一个根据定义生成的数字。
最后如果找不到那个citations[mid] == n - mid的数，那就说明H指数并不在数组中存在，因为我们始终会去找到H指数，然后在找到的基础上进行继续缩小范围，最后low指向的是可以形成H指数的数，或是第一个数，high与low相等，这时候low会加一从而退出循环，因此我们最后要返回n-low。
代码如下:

class Solution {
    public int hIndex(int[] citations) {
        
        int high = citations.length - 1;
        int low = 0;
        int n = citations.length;
        while (low <= high){
            int mid = (high - low) / 2 + low;
            int notLessThanMid = n - mid;
            if (citations[mid] == notLessThanMid )
                return n - mid;
            else if (citations[mid] < notLessThanMid){               
                low = mid + 1;
            }
            else if (citations[mid] > notLessThanMid){
                high = mid - 1;
            }
        }
        return n - low;

    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/h-index-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。