CODEWITHSUNDEEP
algorithmbig-o
Mosho
Mosho

Reputation: 7078

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

This is for an assignment, 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!

Upvotes: 1

Views: 336

Answers (2)

Jaroslav Moravec
Jaroslav Moravec

Reputation: 428

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

Upvotes: 1

adhanlon
adhanlon

Reputation: 6539

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.

Upvotes: 0

Related Questions