why my O(n) solution is slower than O(nlogn) solution?


  • 1
    T
    /*
    basic idea: counting sort
    time: O(n)
    space: O(n)
    */
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            unordered_map<int, int> mp;
            int n = citations.size();
            for (auto i : citations) 
                mp[min(n, i)]++;
            for (int i = n, tmp = 0; i >= 0; i--) {
                tmp += mp[i];
                if (tmp >= i)
                    return i;
            }
            return 0;
        }
    };
    

    This one takes 8ms.

    /*
    basic idea: sort, then find the biggest square
    time: O(nlog(n))
    space: O(1)
    */
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            sort(citations.begin(), citations.end());
            int n = citations.size(), i = n - 1;
            while (i >= 0) {
                if (citations[i] < n - i)
                    return n - i - 1;
                i--;
            }
            return n;
        }
    };
    

    This one takes 4ms.


  • 0

    @Tsien Very impressive solution!

    As for your problem, high-level object in C++ is always inefficient compared to C-way method. So if you change your map into an array here, it will be much better 4-ms result.

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

  • 0
    T

    oh, i see. Thank you :)


Log in to reply
 

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