Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

best way to delete duplicate

 
Edward Chen
Ranch Hand
Posts: 798
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
what is the best way to delete duplicate in this scenario ?

If two elements in a collection, next to each other, has same values, then delete one. For example, in a array [1, 1, 2, 3, 3, 1], we should get [1, 2, 3, 1].

Thanks.
 
Prateek Parekh
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One way would be to convert the array into a Tree Set.
 
Edward Chen
Ranch Hand
Posts: 798
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prateek Parekh wrote:One way would be to convert the array into a Tree Set.

TreeSet is not right. It will delete all duplicate and sorted. Please see the example. we need [1,2,3,1].
 
pete stein
Bartender
Posts: 1561
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why not just iterate through the collection, saving the current item, deleting any duplicates and copying any non-duplicates (and also changing the "current item") as you go? It seems like it should be fairly straightforward to write a method to do this.
 
Rob Spoor
Sheriff
Pie
Posts: 20550
57
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pete's right. Simply iterate through the list, removing the current element if it's the same as the previous. Use an Iterator with it's remove() method as that's the easiest.
 
Edward Chen
Ranch Hand
Posts: 798
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rob Prime wrote:Pete's right. Simply iterate through the list, removing the current element if it's the same as the previous. Use an Iterator with it's remove() method as that's the easiest.


Thanks. I tried it. But it throws java.lang.UnsupportedOperationException, List not support this delete()?

 
John de Michele
Rancher
Posts: 600
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Edward:

Try the remove() method.

John.
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
change this
line to

the problem is Arrays has static inner class called ArrayList in which remove method not supported . but Iterator trying to use that so UnsupportedOperationException.

java.util.ArrayList has an implementation for remove method

hth
 
Paul Clapham
Sheriff
Posts: 21135
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Exactly! As the documentation for Arrays.asList() says:

Returns a fixed-size list backed by the specified array.


Meaning that you can't remove entries from that (fixed-size) list. But Seetharaman's suggestion of copying the fixed-size list into a new list takes care of that problem.
 
Rob Spoor
Sheriff
Pie
Posts: 20550
57
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Edward Chen wrote:

Nice try but highly error-prone. You are calling iterator.next() the second time without checking if there is still a next element. With an odd number of elements that will fail miserably with a NoSuchElementException.

Instead, set the "previous" value before the loop once; you must ensure that the list is not empty first. Inside the loop get the next one, do the comparison, then overwrite the previous value with the current one and continue all over:
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rob Prime wrote:
String previous = iterator.next(); // only possible if the list is not empty


Hi rob, good logic. but here you can simply put String previous = null; right? any way you are assigning next to previous inside loop

like below


 
Rob Spoor
Sheriff
Pie
Posts: 20550
57
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also possible, but don't forget the null check inside the loop.
 
Edward Chen
Ranch Hand
Posts: 798
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:Exactly! As the documentation for Arrays.asList() says:

Meaning that you can't remove entries from that (fixed-size) list. But Seetharaman's suggestion of copying the fixed-size list into a new list takes care of that problem.


I made this change , it works. but it has bug. result will be [1, 1, 2, 3, 1]. I doubt that one List is not enough to handle this job, I need another list to hold it and compare the value.

Thanks.
 
Rob Spoor
Sheriff
Pie
Posts: 20550
57
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's not what I get. With a combination of your new code (using previous = null) and your old code I get [1, 2, 3, 1] as a result. Can you show us the new code?
 
Edward Chen
Ranch Hand
Posts: 798
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rob Prime wrote:That's not what I get. With a combination of your new code (using previous = null) and your old code I get [1, 2, 3, 1] as a result. Can you show us the new code?

Now I got it.

Coding is like this .

I don't understand this in first version. If equals, then remove, why we still need "previous = next " ?

Thanks.


I have made another version, use two arrays
>
 
Rob Spoor
Sheriff
Pie
Posts: 20550
57
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Edward Chen wrote:I don't understand this in first version. If equals, then remove, why we still need "previous = next " ?

You can leave it out if and only if you remove the element; otherwise you'll need to add it or you will compare everything to null.
However, if next.equals(previous), then calling "previous = next" can be considered as an identity statement - you're overwriting previous with the same value*. I just added it to avoid the else block (I'm lazy ), and the result is the same because if x.equals(y) and x.equals(z) then y.equals(z) must also return true (provided that equals is written correctly, which is definitely the case for java.lang.String).


* Technically that's not necessarily true, depending on how equals is written. For strings it's a true statement though.
 
Edward Chen
Ranch Hand
Posts: 798
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rob Prime wrote:
Edward Chen wrote:I don't understand this in first version. If equals, then remove, why we still need "previous = next " ?

You can leave it out if and only if you remove the element; otherwise you'll need to add it or you will compare everything to null.
However, if next.equals(previous), then calling "previous = next" can be considered as an identity statement - you're overwriting previous with the same value*. I just added it to avoid the else block (I'm lazy ), and the result is the same because if x.equals(y) and x.equals(z) then y.equals(z) must also return true (provided that equals is written correctly, which is definitely the case for java.lang.String).


* Technically that's not necessarily true, depending on how equals is written. For strings it's a true statement though.


Thanks everyone for your inputs. I learn a lot.

If-Else version will make it easier to understand. If equal, remove, else move pointer to next one.

If use For-loop, is it possible ?

Thanks.

 
Rob Spoor
Sheriff
Pie
Posts: 20550
57
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It depends on how you write the for-loop. Why don't you give it a try?
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

In Scala it would be 4 lines of code, and 1 for the call.

With generic type, it's nearly the same thing:


If you prefer Arrays, it wouldn't harm much - convert them on the fly to List and the result back again:


Trying to transfer that elegant solutions leads to ugly boilerplate-code:

which is not even generic. This would lead - I expect - to more annoyances.

Maybe functionalJava would help here, or I missed the opportunity, to make my code more elegant.

btw.: Small l and 1 look almost identical in code-blocks. Is this a javaranch-issue or a firefox-linux? There should be a more coderfriendly font, because I used 'l' in my example, and it looked like 1 all over the place. Of course, in longer identifiers like 'long' it's easy distinguishable.

I should search for a better place to ask that? I do!
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic