Alexander Molchevskyi
1 min readMar 22, 2020

--

Your Lesson_06/Distinct looks short and cute but std::set::insert() has O(log(set size)) for insertion of one element and O(N*log(size+N)) for insertion of N elements.

In contrast std::unordered_set::find has constant complexity in this case.

But thanks to you I thought about this task again and found that it is enough to write the solution in one line. It will do the same, will have the same complexity but will looks better and shorter.

int count_distinct(vector<int> &v) {
return std::unordered_set<int>(v.begin(), v.end()).size();
}

Thank you very much for improvement of the article.

--

--

Responses (1)