H-Index I, II

相关题目:

H-Index

注意 LeetCode 给的 Hint:

  • What are the possible values of h-index?
  • A faster approach is to use extra space.

思考 $h$-index 的定义:

  1. 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
  2. if there are several possible values for $h$, the maximum one is taken as the $h$-index.

通过观察,可以发现 $h$ 的取值范围在 $(0, N)$ 之间,是符合以下条件的最大值

  • $h \leq A[h]$, $A[h]$ is the number of papers with citations at least $h$.

基于这个观察,H-Index 这题有两种解法:

  1. Sort and compare: $O(n \log n)$
  2. With auxiliary array for counting papers: $O(n)$

Sort-base 方法

感觉没啥好讲的, 就是 corner case 的处理:

class Solution {  
 public:
  int hIndex(vector<int>& citations) {
    // reversed sort.
    sort(citations.rbegin(), citations.rend());
    // find the first invalid h.
    for (int h = 1; h <= citations.size(); ++h) {
      if (citations[h - 1] < h) {
        return h - 1;
      }
    }
    // corner case.
    return citations.size();
  }
};

Auxiliary Array 方法

根据观察,构建 array $A$,$A[h]$ 保存 at least with $h$ citations 的 paper 数,然后从 $N$ 到 $0$ 扫一遍,结果就出来了.

class Solution {  
 public:
  int hIndex(vector<int>& citations) {
    const int n = citations.size();

    vector<int> A(n + 2, 0);
    for (int num : citations) {
      // round to n.
      num = min(num, n);
      ++A[num];
    }

    int h = 0;
    for (int i = n; i >= 1; --i) {
      A[i] += A[i + 1];
      if (i <= A[i]) {
        h = max(h, i);
      }
    }
    return h;
  }
};

H-Index II

没什么好讲的,直接上 Binary Search。

class Solution {  
public:  
  int hIndex(vector<int> &citations) {
    const int n = citations.size();
    if (n == 0 || citations[n - 1] == 0) {
      return 0;
    }

    // binary search.
    int lo = 0, hi = n - 1;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      int h = n - mid;

      if (h <= citations[mid]) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    return n - lo;
  }
};