Checking array duplication in linear time

Question

Is there any algorithm using comparisons that check array duplication in O(n) time limit?

I.e., Suppose we have a array of type double. Then I need a function like this

bool has_duplicate(double *arr, int len)

that works in O(n) time in the worst case and checks whether it has to equal elements or not.

Please include a proof, if possible.

Answer 1

If you use a data structure that doesn't allow duplicates, then you can do it in O(1) time and O(n) space.

But for a given array, you can put each element in a hashtable (that way iterating the array once), and getting your O(n) time. Along the way looking for collisions, O(1) lookup (average) for hash tables. Although, you will be using more space in the process.

edit: Worst case O(n)? Then you don't want this, use a bit-set as the data structure, but the principle is the same. Proof? I think the people here have given you enough information for you to explore what a proof of complexity is and a foundation of the data structures to look at first. I see no reason why you can't solve the rest of this on your own. Ask follow-ups if necessary, but indicate you understand this, and you made some god damn effort. I do not wish you a Merry Xmas or Happy Holiday, good day to you sir.

edit: I SAID GOOD DAY!

Answer 2

Only in certain circumstances. For example. If you knew the elements in the array could only be numbers between 0 and 9.

You could create a second array of booleans with 10 slots for these possible 10 values. Mark all the booleans false.

Then you could run once through the array you want to test. If you see a number, mark its position (by setting the value to true) in the second 'possible values' array. But before marking it, check if it's already marked. If it was already marked you've got a duplicate. If you get to the end of the array you've tested and no number was already marked in the second 'possible values' array, there's no duplicate.

So, in the general case the answer is "no". But, if you know the possible values that you can have in the array, and you've got enough memory to store a mark for each of these possible values, then "yes".

Answer 3

With an assumption that the value are in limited integer range, you can implement something similar to Bucket Sort to check for duplicate.

int bucket[100] = {0};
int val[] = {1,2,33,10,55,1,45,98};

for(int i = 0 ; i < count ; i++)
    if(++bucket[val[i]] > 1)
        // it's duplicate

Answer 4

If you don't mind giving up some space for a hashset you can get pretty darn close (pseudocode follows):

boolean dupeChecker(values[]){
  set = new hashset();
  for(value : values){
    if(set.contains(value)){
      return true;//there is a dupe
    }
    set.put(value)
  }
  return false;//no dupe
}

You could easily modify this to return the index or indices of duplicate items.

Answer 5

If you must check often but rarely insert, the solution is to sort the array. After sorting, you can find duplicates in O(n) by comparing neighbours (element i and i+1). Use binary search to insert new elements or, if you have a setup stage, insert all elements and then sort them once.

The same applies if you need to compare two arrays: Sort them both. Compare them using two indexes i and j. Advance i if array1[i] < array2[j]. If array1[i] == array2[j], then you have found a common element, else advance j.

If either index runs out of elements, there are no duplicates.

Answer 6

No      

Answer 7

http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html

Have fun!

PS: giyf :)