Using list will make your C++ code much faster!!!


  • 0
    W

    There are a lot of brilliant answers out there. But I noticed that many of them using vector to store the output. However, as stated in official documentation of C++, "Compared to other base standard sequence containers (array, vector and deque), lists perform generally better in inserting, extracting and moving elements". Therefore, we should use a list to store the output that are generated by our algorithm and create the ultimate solution using the list. For example, we have a beautiful solution below:

    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            sort(people.begin(), people.end(),[](pair<int,int> p1, pair<int,int> p2){
                return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
            });
            vector<pair<int,int>> sol;
            for (auto person : people){
                sol.insert(sol.begin() + person.second, person);
            }
            return sol;
      }
    

    This solution runs in 76 ms.
    However, if we use a list as a temporary container. We can reduce the running time to 46 ms, which beats a lot of solutions.

    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            sort(people.begin(), people.end(),[](pair<int,int> p1, pair<int,int> p2){
                return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
            });
            list<pair<int,int>> sol;
            for (auto person : people){
                auto iter = sol.begin();
                advance(iter, person.second);
                sol.insert(iter, person);
            }
            return  vector<pair<int, int>>(sol.begin(), sol.end());
     }
    

    BTW, I want to explicitly state that the worst case time complexity of the latter algorithm is still O(n^2). Even if sorting takes O(nlogn), the second procedure still takes O(n^2). Because the iterator of list container is not random access iterator, so the time complexity of "advance()" is linear time, and that's why we cannot do like this "sol.begin() + person.second". List-based solution is better than vector-based solution, because there are a lot of moving operations (when inserting element) in the latter.


Log in to reply
 

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