ansaurus

Question

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

Answer 1

A:

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.

Silmaril89 2010-05-19 16:01:33

OMG. and what is complexity of "keeping track"?

Andrey 2010-05-19 16:02:36

I think you mean some kind of hashing? That's what I thought about at least, but I don't think it is allowed.

Mosho 2010-05-19 16:08:45

I was actually, thinking something more like what Moravec posted, using a different array to "keep track". And @Andrey, you can keep track of the elements this way with no extra complexity.

Silmaril89 2010-05-19 16:34:57

@Silmaril89 - really? ok, i will be less sarcastic. O(n) means that you will do a constant time operation on each element. There is no way to check tracking of something in constant time. Except if you build hashmap before, but building hashmap has it's own complexity.

Andrey 2010-05-19 16:50:13

@Andrey, What is the complexity of Moravec's answer?

Silmaril89 2010-05-19 16:57:31

@Silmaril89 it is obviously O(n), BUT: 1) it is not general. it works only on numbers 2) it will work on small range of numbers otherwise the memory overhead will be enormous. it is not proper just mentioning keeping track of elements without specifying the way.

Andrey 2010-05-19 17:08:26

@Andrey, sure, but I don't think it's proper for someone to get the entire answer if it is for homework (they won't learn anything if they get the answer). But, I agree with what you are saying. So, let's stop this useless argument and be friends!

Silmaril89 2010-05-19 17:11:11

@Silmaril89 agree :) i just got a feeling that you are giving wrong directions to younger generation

Andrey 2010-05-19 17:13:47

Answer 2

+1 A:

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

Jaroslav Moravec 2010-05-19 16:09:47

I think that does it, thanks alot!

Mosho 2010-05-19 16:14:03

@Mosho: A similar technique can be used to [sort an array in O(n+k)](http://en.wikipedia.org/wiki/Counting_sort)

BlueRaja - Danny Pflughoeft 2010-05-19 16:15:58

That's exactly what I originally had in mind, but it wasn't good enough.

Mosho 2010-05-19 16:32:03

@Moravec and if range is unsigned integer you are going to allocate 4 Gbs ?

Andrey 2010-05-19 17:04:40

@Andrey, the question wasn't about wasteful memory usage, but time complexity. Yes, I agree, unique would have to be a huge array, but it would meet the time complexity requirement.

Silmaril89 2010-05-19 17:07:49

@Andrey: @Silmaril89 answered. And we can't know how the array is implemented. And in the end you can use other data structure as List etc.

Jaroslav Moravec 2010-05-19 18:21:24

Answer 3

A:

If you used only comparisons, there can be no O(n) algorithm.

If it had, then you could solve the Element Uniqueness Problem in O(n) time which has provable Omega(nlogn) lower bounds in the comparison model.

Moron 2010-08-12 06:47:50

ansaurus

tags:

views:

answers:

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

related questions