1 line Ruby, 5 lines C++, 6 lines Java


  • 4

    I saw the picture in the Wikipedia article and thought I'll just count the papers above the diagonal (first sort by decreasing citation number, then count the papers whose citation number is larger than their array index).


    Ruby

    def h_index(citations)
      citations.sort.reverse.each_with_index.count(&:>)
    end
    

    C++

    int hIndex(vector<int>& citations) {
        sort(citations.rbegin(), citations.rend());
        int h = 0, i = 0;
        for (int c : citations)
            h += c > i++;
        return h;
    }
    

    Java

    Since Java doesn't let me sort in reverse order nicely, I sort in normal order and reverse the array indexes instead.

    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length;
        for (int c : citations)
            if (c > --i)
                ++h;
        return h;
    }

  • 0
    M

    Could you please give a little bit explanation about your code.
    I didn't get the for loop part. Thanks.


  • 0

    After sorting the papers (or rather their citation numbers) I just count how many have a higher citation number (c) than index (i). Did you have a look at Wikipedia's picture?


  • 0

    Hi, Stefan. It seems that rbegin and rend are relatively slow. The above C++ code takes 20ms. However, if I translate your Java version into C++, it takes only 12ms.

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            sort(citations.begin(), citations.end()); 
            int h = 0, i = citations.size();
            for (int c : citations)
                h += (c > --i);
            return h;
        }
    };
    

    Update: someone posts a nice O(n)-time solution here (I even do not realize that there is an O(n)-time solution) using O(n) additional memory, which achieves 8ms 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;
        }
    };
    

Log in to reply
 

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