H-Index - LeetCode

https://leetcode.com/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode_Sharing.png

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 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, their h-index is 3.

Example 2:

Input: citations = [1,3,1]
Output: 1

Constraints:

  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations[i] <= 1000

解析

Approach:

  1. Bucket Counting: Create an array buckets of length n+1 where n is the length of the citations array. Each element of buckets will store the count of papers with the number of citations equal to the index. If the number of citations for a paper exceeds n, then we increase the count of the last bucket.
  2. Cumulative Sum: Traverse the buckets array from right to left and compute the cumulative sum.
  3. Finding h-index: The h-index is the first index from the right where the cumulative sum is greater than or equal to the index.

创建一个长度为 n+1 的全为 0 的数组，遍历数组， 将对应的数字出现的次数进行统计，假设发表了10篇文章，那么h-index最大值为10，因此大于数组长度的引用次数的可以视为最高值。

统计结束后，反向索引累加，当累加次数大于等于索引，就计算出了h-index.

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        buckets = (n + 1) * [0]

        for cite in citations:
            if cite >= n:
                buckets[n] += 1
            else:
                buckets[cite] += 1
        sum = 0
        for j in range(n, -1, -1):
            sum += buckets[j]
            if sum >= j:
                return j

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] buckets = new int[n + 1];

        for (int cite:citations) {
            if (cite > n){
                buckets[n] += 1;
            }
            else 
            {
                buckets[cite] += 1;    
            }
        }
        int sum = 0;
        for (int i = n; i >= 0 ; i--) {
            sum += buckets[i];
            if (sum >= i){
                return i;
            }
        }
        return 0;
    }
}

class Solution {
public:
    int hIndex(vector<int>& citations) {
    int n = citations.size();
    vector<int> buckets(n + 1, 0);

    for (int cite:citations) {
        if (cite > n){
            buckets[n] ++;
        }
        else
        {
            buckets[cite] ++;
        }
    }
        int sum = 0;
        for (int i = n; i >= 0 ; --i) {
            sum += buckets[i];
            if (sum >= i){
                return i;
            }
        }
    return 0;
    }
};s