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?

暴力 o(n)

 1 class Solution {
 2 public:
 3     int hIndex(vector<int>& citations) {
 4         int max = 0 ;
 5         int size = citations.size() - 1;
 6         for(int i = size;i >= 0; --i) {
 7             int cur_num = size-i + 1;
 8            if(citations[i]>=cur_num) {
 9                max =std::max(max,cur_num);
10            }
11         }
12         return max;
13     }
14 };

二分 log(n)

 1 class Solution {
 2 public:
 3     int hIndex(vector<int>& citations) {
 4         int max = 0 ;
 5         int size = citations.size();
 6         int low = 0;
 7         int high  = size;
 8         while(low < high) {
 9             int mid = low + (high - low) / 2;
10             int cur_num = size-mid ;
11            if(citations[mid]>=cur_num) {
12                high = mid;
13                max =std::max(max,cur_num);
14            } else {
15                low = mid+1;
16            }
17         }
18         return max;
19     }
20 };