O(n) Java solution using O(n) space


  • 23
    T

    Explanation: The idea is to use another array, index is the citation and value is the number of papers that has at least the citation. Since the h-index can only be n, the new array will only need the index to be at most n, thus the array size will only need n+1. Papers that have more than n citations will store in array[n].
    Go through the array based on h index definition: array[i]>=i, find the max value of i.

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

  • -2
    S

    Hi,

    I came across a situation: given citations = [3, 1, 7, 8, 9]. What will be the answer be?

    According to the definition of h-index on Wikipedia: "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."

    When h=3, the definition will be "A scientist has index 3 if 3 of his/her 5 papers have at least 3 citations each, and the other 2 papers have no more than 3 citations each." Obviously wrong....

    When h=4, the definition will be "A scientist has index 4 if 4 of his/her 5 papers have at least 4 citations each, and the other 1 papers have no more than 4 citations each." Obviously wrong....

    When h=2, the definition will be "A scientist has index 2 if 2 of his/her 5 papers have at least 2 citations each, and the other 3 papers have no more than 3 citations each." Obviously wrong....


  • 0
    T

    h index would be 3 in this case. As 7,8,9>=3 and 1,3 <=3 (The definition of h index "...no more than")


  • 0
    W

    yeah, exact same idea as mine :)


  • 0
    S

    There is one way you can simplify it by removing if(num[n]>=n) return n;
    In that case, instead of overriting in num array, you can maintain an integer sum = 0 and start from length index.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.