Finding Duplicate Elements

Suyash Upadhyay

How to find more than one duplicate elements in array? ( One method is BST, but I want efficient method than it)

weaknessforcats

You may have to do a progressive loop where you start with element 0 and traverse the array looking for dupluicates. Then start with element 1, etc.

If duplicates is an error condition, and you are in C++, then use a set<> container, which does not allow duplicates. At run time if the insert fails, the new value is a duplicate. Of course, set<> uses a red/black tree, but there you are.

Suyash Upadhyay

Quote:

Originally Posted by weaknessforcats

You may have to do a progressive loop where you start with element 0 and traverse the array looking for dupluicates. Then start with element 1, etc.

If duplicates is an error condition, and you are in C++, then use a set<> container, which does not allow duplicates. At run time if the insert fails, the new value is a duplicate. Of course, set<> uses a red/black tree, but there you are.

I am aware of set<> but I want to search algorithm better than O(n^2) and algorithm proposed is O(n^2). Cann't we make it better?

weaknessforcats

You might need a hash chain-link table.

That is, an array of linked lists. At least you would only have to traverse the list of elements that had the same hash value.

I think Robert Sedgewick ("Algorithms in C++") calls this separate chaining. It's been a long time.

Finding Duplicate Elements

re: Finding Duplicate Elements

re: Finding Duplicate Elements

re: Finding Duplicate Elements

Similar C / C++ bytes

/bytes/development

/bytes/it

/bytes/about