[LeetCode] 275. H-Index II

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."

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?

H指数II。题意跟版本一差不多，本题已经帮你把input排好序了，并且题目要求时间复杂度需要在log级别，所以思路自然而然是二分法。

但是这个题如何做二分呢？首先因为input已经排好序，所以要比较的应该是citations[mid]和len - mid的关系。citations[mid]背后的含义是第mid篇文章被引用的次数；而len - mid的含义则要参考H指数的定义，

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.

所以还是参考这个图。如果citations[mid]正好等于len - mid则return mid；但是如果两者不等，则按照二分法正常的规则往中间逼近。注意最后返回的是len - left，代表h指数。

时间O(logn)

空间O(1)

Java实现

 1 class Solution {
 2     public int hIndex(int[] citations) {
 3         int len = citations.length;
 4         int left = 0;
 5         int right = len - 1;
 6         while (left <= right) {
 7             int mid = left + (right - left) / 2;
 8             if (citations[mid] == len - mid) {
 9                 return len - mid;
10             } else if (citations[mid] < len - mid) {
11                 left = mid + 1;
12             } else {
13                 right = mid - 1;
14             }
15         }
16         return len - left;
17     }
18 }