• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Optimized way of finding duplicate elements in the array?

 
Ranch Hand
Posts: 1491
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Saloon Keeper
Posts: 14515
325
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 1491
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ?
 
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 14515
325
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 14515
325
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Are you okay? You look a little big. Maybe this tiny ad will help:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic