Why sort is faster than set?


  • 0
    G

    Two solutions: 1) use sort and unique (40ms)

    sort(nums.begin(),nums.end());
    return unique(nums.begin(), nums.end()) != nums.end();
    
    1. use set (48ms)

      set<int> s(nums.begin(), nums.end());
      return s.size() != nums.size();

    My question is why "sort" solution is faster than "set" solution????? In my mind, "set" solution is O(n), while "sort" solution is at least O(nlogn).


  • 0
    P

    I think std::set is implemented as Red-Black tree, whose construction is still O(nlogn).


  • 0
    N

    unordered_set is still slower than sort(). I can only assume that the test case set is so small that set library can't take advantage of time computation.


Log in to reply
 

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