【leetcode】275. H index II

subject ：

 Give you an array of integers  citations , among  citations[i]  Indicates the researcher's second opinion  i  The number of citations of this paper ,citations  According to   Ascending order  . Calculate and return the researcher's  h  Index .
h  The definition of index ：h  representative “ High citations ”（high citations）, A researcher's  h  The index refers to him （ she ） Of  （n  In a paper ） All in all  h  At least one of the papers was cited  h  Time . And the rest  n - h  Number of citations per paper   No more than  h  Time .

 Tips ： If  h  There are many possible values ,h  Index   It's the biggest one .

 Please design and implement an algorithm with logarithmic time complexity to solve this problem .

 Example  1：

 Input ：citations = [0,1,3,5,6]
 Output ：3 
 explain ： The given array indicates that the researcher has a total of  5  Papers , Each paper is cited accordingly  0, 1, 3, 5, 6  Time .
      Because the researchers have  3  Each paper   At least   It's quoted  3  Time , The other two papers are cited   Not more than  3  Time , So her  h  The index is  3 .
 Example  2：

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

Method 1 ：

violence

class Solution {
    
    public int hIndex(int[] citations) {
    
        int n = citations.length;
        int count = 0;
        for(int i = n-1; i>= 0;i--){
    
            if(count >= citations[i]) return count;
            count++; 
        }
        return count;
    }
}    

Method 2 ：

Two points
The question ： For the biggest h, Make the array have h Elements are not less than h

class Solution {
    
    public int hIndex(int[] citations) {
    
/**  Dichotomy ： */
        int n = citations.length;
        int l = 0, r = n - 1;
        while(l <= r){
    
            int mid = (l+r) / 2;
            // len - mid  For from mid To len To the number of papers , If you want to len - mid As hIndex
            //  It is required to start from mid To len The lowest cited paper in citations Is greater than or equal to len - mid（ That is to say citations[mid]>=paperCnt）.
            //  If this condition is met , Let's try to make hIndex Bigger , That is to say mid To the left , Then let's adjust end = mid - 1
            //  If the conditions are not met , We let mid Move to the right , such paperCnt Less , meanwhile citations[mid] It's big too , Let's look again from mid Start to len Can you act as hIndex
            if(citations[mid] >= n - mid) r = mid - 1;
            else l = mid + 1;
        }   
        return n - l;
    }
}