I have an array of integers. I want to find all the distinct elements in the array using c++. solutin 1: BRUTE FORCE using nested loop, complexity of this solution is O(n^2)
solution 2: SORTING this will take O(nLog n)
Is there any other technique which can give better results than O(n Log n)? any other data structure or any different technique?
Using a std::unordered_set will be O(n).
You can also try using std::nth_element: It partially sorts the range [first, n-th, last) such that all entries in the interval [first, n-th) are <= n-th, and all elements in the interval (n-th, last) are >= than n-th. It has linear complexity (O(n)), and will find the n-th element in a sequence. It's not suited to find a specific number, though, so maybe it's not exactly what you need. But it's worth to keep it in mind :-)
If you know the maximum integer number, and it is reasonably small, you cann allocate a large vector and use that to count the frequency of each integer. Then, iterate over the vector and find all with frequency one:
template<typename I>
auto findWithFrequency(int f, int max, I first, I last)
{
std::vector<int> counts(max, 0);
for(; first != last; ++first)
{
counts[*first] += 1;
}
std::vector<typename I::value_type> v;
v.reserve( std::distance(first, last) );
std::copy_if(counts.begin(), counts.end(),
std::back_inserter(v),
[f](auto x) {return x == f;});
return v;
}
In the worst case, this needs two iterations over arrays of the size of the input array, so the complexity is O(n).
This is essentially the idea behind Bucketsort or Radix.
