275 H-index II

第一种方法：线性搜索。

第二种方法：二分搜索。将问题简化为给一个大小为n的递增序列，找到第一个元素能够满足这个关系citations[i] >= n-i。

Java

Method 1

class Solution {
    public int hIndex(int[] citations) {
        int idx = 0;
        int n = citations.length;
        for(int c: citations){
            if(c >= n - idx)
                return n - idx;
            else
                idx ++;
        }
        return 0;
    }
}

Method 2

class Solution {
  public int hIndex(int[] citations) {
    int idx = 0, n = citations.length;
    int pivot, left = 0, right = n - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (citations[pivot] == n - pivot) return n - pivot;
      else if (citations[pivot] < n - pivot) left = pivot + 1;
      else right = pivot - 1;
    }
    return n - left;
  }
}