Optimal way of finding whether any element is repeated in a given array?

What is the 开发者_JAVA技巧best optimal way of finding whether any element is repeated in a given array?

Put the elements in a hashtable, doing value equality comparisons on any collisions.

If we consider that the duplicates may more than two for case like: {2,3,2,2,2,5,5,7,7},here we need to build an hash table and then look for the non duplicates

Using STL map container it becomes a very easy job: (The question was not tagged to C++ but STL will make the hashing job clean) It can also handle cases all unique cases.

  #include <iostream>
  #include <vector>
  #include <iterator>
  #include <map>
  using namespace std;

 int main(void){
      map<int,int> array;
      map<int,int>::iterator ii;

    int arr[] = {2,3,5};
    vector<int> unique_list;
    int size = sizeof(arr)/sizeof(arr[0]);

    for(int i = 0; i<size; i++)
          ++array[arr[i]];

     bool flag = false;

    for(ii=array.begin();ii != array.end(); ++ii)
     if(ii->second == 1){
         flag = true;
         unique_list.push_back(ii -> first);
       }

   if(flag == true){
      cout<<"Unique element(s): ";
      copy(unique_list.begin(),unique_list.end(),ostream_iterator<int>(cout," "));
     }
   else
     cout<<"All elements have dulicate"<<endl;

   return 0;
 }

The complexity is O(n) so it is still in Linear time.

Most other answers mention hashtables, and are actually optimal since it gets the job done in O(n).

Another way to do it, without using hashtables. Simply sort the array (using qsort) and the iterate over the elements checking if two adjacent elements are the same. Sorting makes same elements group together and so makes checking for duplicates easy. Of course, this is O(nlog) and will change the order of the original array, but is a lot shorter and saves you the trouble of coding a hashtable.

In general, it is an O(n) problem. You need to check each element, usually using a hashtable. If it is sorted, you can just look one to the left and one to the right.

I think a Bloom Filter fits the problem well, probably with a lower space requirement than a hash table would need. (although it does have possible false positives)

Might not be the solution you're looking for, but:

• if the elements are integers
• and if you know their maximum possible value MAX,

build an array DUPS of size [MAX] where each element is zero; parse the original array ORIG, and for each element i:

int i;
for ( i = 0 ; i < DUPS_SIZE ; i++ )
    if ( DUPS[ORIG[i]] == 1 ) 
        return true; /* the original array has duplicate elements */
    else
        DUPS[ORIG] = 1;
return false;

Or you can iterate through ORIG in a random order. Worst case is still O(DUPS_SIZE).