StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First of all, there is no need for a map, a set is conceptually more correct, since you don't want to store any values, but only the keys.</p> <p>Performance-wise, it might be a better idea to use a <code>std::unordered_set</code> instead of a <code>std::set</code>, as the former is hashed and can give you O(1) insert and lookup in best case, whereas the latter is a binary search tree, giving you only O(log n) access.</p> <pre><code>vector<int> uniqueArr(int arr[], int size) { std::unordered_set<int> storedValues; vector<int> uniqueArr; for(int i=0; i<size; ++i){ if(storedValues.insert(arr[i]).second) uniqueArr.push_back(arr[i]); return uniqueArr; } </code></pre> <p>But if you are allowed to use the C++ standard library more extensively, you may also consider the other answers using <code>std::sort</code> and <code>std::unique</code>, although they are <strong>O(n log n)</strong> (instead of the above <strong>~O(n)</strong> solution) and destroy the order of the elements.</p> <hr> <p>If you want to use a more flexible and std-driven approach but with ~O(n) complexity and without destroying the order of the elements, you can transform the above routine into the following std-like algorithm, even if being a bit too far-fetched for a simple interview question:</p> <pre><code>template<typename ForwardIterator> ForwardIterator unordered_unique(ForwardIterator first, ForwardIterator last) { typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; std::unordered_set<value_type> unique; return std::remove_if(first, last, [&unique](const value_type &arg) mutable -> bool { return !unique.insert(arg).second; }); } </code></pre> <p>Which you can then apply like <code>std::unique</code> in the usual erase-remove way:</p> <pre><code>std::vector<int> values(...); values.erase(unordered_unique(values.begin(), values.end()), values.end()); </code></pre> <p>To remove the unique values without copying the vector and without needing to sort it beforehand.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload