[LeetCode] 275. H-Index II

[frdmu]

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in an ascending order, return compute the researcher's h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

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

You must write an algorithm that runs in logarithmic time.

 
Example 1:

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, their h-index is 3.

Example 2:

Input: citations = [1,2,100]
Output: 2

Constraints:

• n == citations.length
• 1 <= n <= 105
• 0 <= citations[i] <= 1000
• citations is sorted in ascending order.

 
 
 
题目的思路274. H-Index是一样的，按照维基百科上的算法：

• 1.先把数组降序排列
• 2.再遍历数组，如果citations[i] > i，h++

区别就是本题已经把数组升序排列好了，需要转化一下，举个例子：

citations	0 1 3 5 6	(1)
升序索引	0 1 2 3 4	(2)
降序索引	4 3 2 1 0	(3)

现在如果只看(1)和(3)，就会发现，它和274. H-Index是一样的，即(注意对应关系，比如6->0，5->1...)：

citations	6 5 3 1 0	(1)
降序索引	0 1 2 3 4	(3)

不难看出，满足citations[i] > i的共有3个。

而(2)和(3)之间是有关系的，即 (2) + (3) = n-1。如0+4 = 1+3 = 4
所以问题就从

274. H-Index的citations[i] > i	(4)

变为现在的

citations[i] > n-1-i	(5)

如同样是满足citations[i] > i, 对于5>1，在降序序列中是citations[1] > 1，在升序序列中就变为citations[3]> 4-3

所以问题就转化为在citations = [0,1,3,5,6]中寻找第一个citations[i] > n-1-i 的元素，且h = n-该元素的索引。
这里可以直接套用LeetCode Binary Search Summary 二分搜索法小结第三类模板，代码如下：

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size(); 
        int left = 0, right = n;

        while (left < right) {
            int mid = left + (right - left) / 2; 
            if (citations[mid] <= n-1-mid) left = mid + 1;
            else right = mid;
        }

        return n - right; 
    }
};

Refer:grandyang/leetcode#275