if the number of items can be quantified in a simple way, counting sort solves this in one pass.
basically
int ctsrt[number of items]{}; //eg, say your data is 0-5 or whatever, number of items is 6, right?
then
for(all the data && !hazdupz)
{
ctsrt[data]++;
if(ctsrt[data] > 1)
hazdupz = true;
}
counting sort can be replaced with a variety of things with O(1) lookup time if a C array offends you or if the data is not simply quantified. a derpy check can be used if it is simply quantifiable as well: if you have 0-5 possible values, and the vector size > 6, you must therefore have a duplicate. The reverse is not ensured, of course.
If the unique set method is used, then doing a checked insert loop is more efficient as it terminates when a duplicate is found - rather than building the entire set and then checking it's number of elements:
As jonnin says, if the range of the vector elements is constrained to be within a smallish range, then direct counting can be done. In this example, the range is restricted to simply a unit8_t type - which has a range of 0 - 255 (ie 256 elements):
@ihavesmallbrain - is this just an exercise/test or is this for production code? If for production code, approx how many elements are we dealing with? ie is potential performance an issue?
Sorting the vector and operating on it is O(n log n). Brute forcing the duplicates check is O(n^2), but may be faster for smaller n. As usual, would need to measure with real data for your use case. [And if the range of the numbers is bounded, then you could say it's O(n), to create and iterate over the necessary array.]
It doesn't have to be bounded to get N. Its just easier to explain and code it for beginners. Any O(1) retrieval approach can stow and count less friendly data.
my approach is O(n^2) which is time limit exceeded, should I sort the vector first or use an unordered_set, which method is faster and use less space ?
> The tese cases are hidden so I don't know how big is the vector
So create your own large test cases.
Eg
1 2
std::vector<int> tests;
for ( int i = 0 ; i < 1E6 ; i++) tests.push_back(i);
This creates a test with no duplicates.
You can then mutate it with say to make two elements the same.
tests[1000] = tests[100000];
Both approaches presented above should be fine.
Sorting is perhaps simpler, as it doesn't involve creating new data, if you're allowed to modify the vector you're given. All the operations seem to be O(N) or O(NlogN), so basically O(NlogN).
> If you can't modify the data, then you're left with the set method.
If we can't modify the data, we can copy it and sort the copy.
For 105 random integers, making a copy and sorting appears to be significantly faster on the average (libstdc++).