A Clean O(N) Solution in Java


  • 86
    J
    public int hIndex(int[] citations) {
        int len = citations.length;
        int[] count = new int[len + 1];
        
        for (int c: citations)
            if (c > len) 
                count[len]++;
            else 
                count[c]++;
        
        
        int total = 0;
        for (int i = len; i >= 0; i--) {
            total += count[i];
            if (total >= i)
                return i;
        }
        
        return 0;
    }

  • 6

    Great O(n) code! I rewrite it in C++ :-)

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int n = citations.size(), h = 0;
            int* counts = new int[n + 1]();
            for (int c : citations)
                counts[min(c, n)]++;
            for (int i = n; i; i--) {
                h += counts[i];
                if (h >= i) return i;
            }  
            return h;
        }
    };

  • 2
    L

    Another way to handle the 2nd loop in C#.

    public int HIndex(int[] citations) {
        int[] counts = new int[citations.Length + 1];
        for(int i = 0; i < citations.Length; i++)
            if(citations[i] >= citations.Length)
                counts[citations.Length]++;
            else counts[citations[i]]++;
        for(int i = 0, countRight = citations.Length; i < counts.Length; i++){
            if(countRight <= i) return countRight;
            countRight -= counts[i];
            if(countRight <= i) return i;
        }
        return 0;
    }

  • 0
    W

    Savvy! How smart it is


  • 0
    M
    This post is deleted!

  • 0
    T

    I don't understand why there might be more than one value for h that can satisfy the definition.
    Can anyone give me an example?


  • 0

    @tianyicai2010 Actually there should be only one solution, if I am not wrong. Suppose there are two different results a and b and a < b in n citations:

    • First, as for b, there are b citations that are bigger or equal to b.
    • Second, as for a, there are a citations that are bigger or equal to a and the rest n-a citations are equal to or less than a;
    • But, since b>a then there are at least b citations that are bigger than a (according to the First) and then at most there will be n-b that are less than or equal to a which is a contradiction against the fact that there will be n-a that is equal to or less than a (according to the Second).

    @administrators Am I right? If so, I think the description of the problem should be corrected A.S.A.P. Thank you! @1337c0d3r


  • 0
    C

    Hi Could you explain your thinking process of how you manage to come up with this solution. It is genius.
    Would be great if you can share the knowledge.

    Thanks,

    Marc


  • 4

    This question is not easy to understand to me. First we come to
    1) The easier solution which given by the wiki page:

    First we order the values of f from the largest to the lowest value.
    Then, we try to find the last number >= its index, its index is the H-index.

    For example, if we have a researcher with 5 publications:
    25, 8, 5, 3, 3 citations respectively,
    1 , 2, 3, 4, 5 as index.

    The number is 5, H-index is 3.

    2) The O(n) solution:
    A researcher have 5 pulications:
    A, B, C, D, E with
    5, 8,10, 4, 3 citation respectively.

    After first loop:

      for (int c: citations)
            if (c > len) 
                count[len]++;
            else 
                count[c]++;
    

    we have the count array:

    value: 0, 0, 0, 1, 1, 3
    index: 0, 1, 2, 3, 4, 5
    

    In second loop:

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

    Step 1: index is 5, total = 3.
    Step 2: index is 4, total = 4, return 4.


  • 0
    R

    Can someone explain to me what are we trying to do in second loop and how are we getting answer?


Log in to reply
 

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