O(n) solution in C with explaination


  • 0
    Y

    we know that for a array of n citations, hIndex can only be [0..n], so use a extra array. for the first pass, it counts all cites, and the second loop tries to find the possible hIndex

    int hIndex(int* cites, int n) {
        int* hs = malloc(sizeof(int) * n + 1);
        // REMEMBER to initialize your array!
        for (int i = 0; i < n + 1; i++)
            hs[i] = 0;
        for (int i = 0; i < n; i++) {
            if (cites[i] > n)
                hs[n]++;
            else
                hs[cites[i]]++;
        }
        
        for (int i = n, papers = 0; i >= 0; i--) {
            papers += hs[i];
            if (papers >= i)
                return i;
        }
        
        return 0;
    }

Log in to reply
 

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