Determine if a number only appears once in an array

Question

This is kind of a homework question, I've been thinking about it for quite a while, and came up with a couple of solutions but I think a better one exists.

What's the fastest way to determine if there is an element (int) in the array that appears only once? Any element can appear any number of times. {3, 1, 4, 1, 4, 3} will return false while {3, 1, 4, 1, 4, 1} would return true (3 appears once).

We are only allowed to use things we already learned (all the basics, recursion, oop, searching and sorting algos, including quicksort) so making a hash table is not an option.

So far the best practical solution I came up with is sorting it using quicksort then going through it ( O(nlogn) ), the best unpractical solution I came up with is making a big array the size of all possible int values and then using it's place similar to a hash table (but that array is WAY too big to actually implement) ( O(n) )

Is there another (practical) way to do this in O(n) time?

EDIT: just got an answer from the TA, the suggested O(n) solution that I heard about was an unpractical one (the same or similar to what I suggested) and hence they told us not to use it. I'm 99% sure now that the best practical answer (without hash tables) is O(nlogn) time.

Answer 1

You could use a customised quicksort to find distinct values without iterating over the sorted array afterwards.

When you have chosen a pivot value and are moving through the respective part of the array, IF the value matches the pivot, discard it AND discard the pivot value after you have moved through the part of the array, this would remove duplicates BEFORE the array is eventually sorted.

ie:

Sorting [5, 1, 4, 1, 4, 1]
If you choose the pivot as 4, you'd end up with the 2 sub arrays being:
[1, 1, 1] and [5]

If your pivot is never discarded, it is distinct, if it is discarded do the same process on the sublists. If a sublist has only 1 element, it is distinct.

In this way you can pick up distinct values MUCH earlier.

Edit: Yes this is still bounded by O(nlogn) ( I think ?)