Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Optimized way of finding duplicate elements in the array?  RSS feed

 
kri shan
Ranch Hand
Posts: 1489
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Taking every element one by one and comparing that element with other elements. Is it optimized approach ? If not, suggest some other way/algorithm.
 
Stephan van Hulst
Saloon Keeper
Posts: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It depends on how your data is stored in the array. For instance, if the data is sorted non-decreasingly, you only have to compare neighbours.

For any old array though, there is not much choice but to compare all the elements.
 
kri shan
Ranch Hand
Posts: 1489
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For instance, if the data is sorted non-decreasingly, you only have to compare neighbours.

If data is not sorted, how to compare elements ?
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
kri shan wrote:If data is not sorted, how to compare elements ?
You could add them one by one to a Set
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joanne Neal wrote:You could add them one by one to a Set

Yes, that would work - check the return value of Set.add() if you want to know which are the duplicates, rather than just removing them.

Or you could sort your collection first.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew Brown wrote:check the return value of Set.add() if you want to know which are the duplicates
I was leaving that as something for the OP to work out
 
Stephan van Hulst
Saloon Keeper
Posts: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note that while perfectly valid, adding items to a Set will still compare each element to all items already contained by the set.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
True, but the Java developers probably spent plenty of time working out an efficient algorithm to do it which means the OP doesn't have to.
 
Stephan van Hulst
Saloon Keeper
Posts: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not really sure, but if I would make an educated guess, I don't think there is an optimized way to do this for any old unsorted array.

Either you compare each element directly, or you add them to some kind of sorted set, which would still compare each element to each other element in order to sort them.


I'm sorry, I didn't have my coffee today. Of course you don't need to compare each element to each element in order to sort them. *face palm*
You're absolutely right Joanne.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!