C++ solution using heap faster than sort!


  • 1
    P
    int hIndex(vector<int>& citations) {
        int len = citations.size(), last = INT_MIN;
        make_heap(citations.begin(),citations.end(),greater<int>());
        for (int h = len;h >0;--h) {
            if (citations[0] >= h && last <= h)
                return h;
            last = citations[0];
            pop_heap(citations.begin(),citations.end()-(len-h),greater<int>());
        }
        return 0;
    }

  • 0

    How much faster?


  • 0
    P

    In my test, it's 8ms vs 12ms. You may say it's still O(nlogn), but it's different from the O(nlogn) of sort. I just want to provide some new thought!


  • 0

    Yeah yeah, it's definitely good, I was just wondering what you meant. I didn't even know whether you meant actual time in milliseconds (and it's nice to know how much) or the complexity class :-). Btw, I guess you could call it O((n-h) log n).


  • 1

    I rewrote it so it searches in the other direction (from most cited papers to least cited papers):

    int hIndex(vector<int>& citations) {
        int len = citations.size();
        make_heap(citations.begin(), citations.end());
        for (int h=0; h<len; ++h) {
            if (citations[0] <= h)
                return h;
            pop_heap(citations.begin(), citations.end()-h);
        }
        return len;
    }
    

    That's then O(h log n) and I was hoping it would be faster than your original, both because I don't use "last" and because I think h should usually be smaller than n-h (like the picture in Wikipedia's article suggests).

    Obsolete: But in the OJ, it's actually slower: 16-20ms vs your 8ms. Sadly, the OJ has rather unrealistic data. It looks random and the only really large case (more than 100 papers) is a case with 10000 papers and the citations are in the millions, so h is 10000 :-(. I need to go through all 10000 papers, you stop right at the start.

    Update: After I pointed this out, the large unrealistic case was replaced with a more realistic one. Now it's 5000 papers and h is around 850. Your solution didn't get worse, it's still at 8 ms, but my version is now at 4 ms (each every time in three attempts).


  • 0
    P

    You are so conscientious! Great job!


Log in to reply
 

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