Two similar C++ codes, but runtime is very different. Why?


  • 0
    B

    Here are my two C++ submissions. They are the same except for a conditional statement, but the runtime is very different:
    code1: 36ms, beats 99.35%
    code2: 48ms, beats 69.79%
    Who can tell me why?

    Code1:

    class Solution
    {
    public:
        int findLongestChain(vector<vector<int> >& pairs)
        {
            int size = pairs.size();
            vector<vector<int>*> pps(size);
            for(int i = 0; i < size; ++i)
            {
                pps[i] = &(pairs[i]);
            }
            sort(pps.begin(), pps.end(), cmp2nd);
            int res = 1;
            int cur2nd = (*(pps[0]))[1];
            for(int i = 1; i < size; ++i)
            {
                vector<int>& p = *(pps[i]);
                if(p[0] <= cur2nd) continue; // Here is different
                res++;
                cur2nd = p[1];
            }
            return res;
        }
        static bool cmp2nd(const vector<int>* p1, const vector<int>* p2)
        {
            return (*p1)[1] < (*p2)[1];
        }
    };
    

    Code2:

    class Solution
    {
    public:
        int findLongestChain(vector<vector<int> >& pairs)
        {
            int size = pairs.size();
            vector<vector<int>*> pps(size);
            for(int i = 0; i < size; ++i)
            {
                pps[i] = &(pairs[i]);
            }
            sort(pps.begin(), pps.end(), cmp2nd);
            int res = 1;
            int cur2nd = (*(pps[0]))[1];
            for(int i = 1; i < size; ++i)
            {
                vector<int>& p = *(pps[i]);
                if(p[0] > cur2nd) // Here is different
                {
                    res++;
                    cur2nd = p[1];
                }
            }
            return res;
        }
        static bool cmp2nd(const vector<int>* p1, const vector<int>* p2)
        {
            return (*p1)[1] < (*p2)[1];
        }
    };
    

Log in to reply
 

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