Counting duplicates (not necessarily removing) in an array in O(n)

This is for an assignme开发者_如何转开发nt, and is in psuedo-code.

I need to find how many integers in an array are unique, nothing else, but it has to be in O(n), preferably without hashing.

Thanks!

What about this pseudo code?

array randomNumbers;
array unique;
int uniqueCount = 0;

for (i in randomNumbers) {

  unique[i] += 1;
  uniqueCount++; //count all here
  // and remove duplicities here
  if (unique[i] > 1) {
    uniqueCount--;
  }
}
return uniqueCount;

And the premis is, that undeclared unique[i] is 0

Just iterate through each element in the array and keep track of the elements you see, when you see a duplicate, report it.

Also, depending on how you keep track of elements, it may or may not be O(n), but I'll leave that part up to you, you got to learn something at least.