274. H-Index

Source link: https://leetcode.com/problems/h-index/

Design

The problem could be solved by applying the bucket sort as the definition of h-index is the last number of papers with reference sorting as the descending order equal or greater than its index.

  1. Assume n is the length of the array citations.
  2. Initialize n + 1 buckets (array buckets).
  3. Traverse through the array citations, once if the number of paper citations is larger than n, increase the count of the last bucket, else increment the count of the buckets[i].
  4. Iterate from the back to front of the array buckets, record the number of citations accumulated, once if the count equal or larger than the index, it will return the h-index result.

Implementation

class Solution {
  public int hIndex(int[] citations) {
    int n = citations.length;
    int[] buckets = new int[n + 1];
    for (int i = 0; i < n; i++) {
      if (citations[i] >= n) {
        buckets[n]++;
      } else {
        buckets[i]++;
      }
    }

    int count = 0;
    for (int i = n; i >= 0; i--) {
      count += buckets[i];
      if (count >= i) {
        return i;
      }
    }
    return 0;
  }
}

Complexity Analysis

Time: $O(n)$

Space: $O(n^2)$