Forums Register Login

Remove duplicates from char array with O(n) complexity

+Pie Number of slices to send: Send
Hi,

I need to write a program to remove duplicates from a char array. The program should be with time complexity O(n).

Example, if word is independence ( as a character array), output should be = indepc

Please let me know how to do this.
+Pie Number of slices to send: Send
Check out LinkedHashSet; use java.lang.Character as the generic type.
+Pie Number of slices to send: Send
Does LinkedHashSet ensures that the duplicates are removed with O(n) complexity?
+Pie Number of slices to send: Send
LinkedHashSet has a (near) constant-time lookup, O(1). The looping and adding takes O(n). As a result, the total is O(n*1) == O(n).
+Pie Number of slices to send: Send
Have you read its documentation?
+Pie Number of slices to send: Send
 

Raj Kumar Bindal wrote:I need to write a program to remove duplicates from a char array. The program should be with time complexity O(n).
Example, if word is independence ( as a character array), output should be = indepc
Please let me know how to do this.


Well a character is a numeric value, so you could create an array of booleans for all possible values; or indeed use a BitSet.

Winston
+Pie Number of slices to send: Send
The biggest problem with that is the number of possible values. While for bytes there are only 256 possible values, for chars that's 65536. With the current implementation of BitSet that requires just 1024 longs, using a boolean[] is probably going to be a lot more memory intensive.

But yeah, the BitSet solution would work. You need two loops (one for setting, one for retrieving) but since these loops will not be nested that's still O(n).
+Pie Number of slices to send: Send
 

Rob Spoor wrote:The biggest problem with that is the number of possible values. While for bytes there are only 256 possible values, for chars that's 65536. With the current implementation of BitSet that requires just 1024 longs, using a boolean[] is probably going to be a lot more memory intensive.


True, but if memory serves, a boolean is the same size as a byte; and what's 64K between friends these days?

But I agree, BitSet is probably the best for a combo of size and speed.

Winston
+Pie Number of slices to send: Send
 

Winston Gutkowski wrote:

Rob Spoor wrote:The biggest problem with that is the number of possible values. While for bytes there are only 256 possible values, for chars that's 65536. With the current implementation of BitSet that requires just 1024 longs, using a boolean[] is probably going to be a lot more memory intensive.


True, but if memory serves, a boolean is the same size as a byte; and what's 64K between friends these days?



Actually, I think it's the size of an int, so 256k. But then again, I thought that that was just for individual booleans, and that boolean arrays were bit-packed.

Or maybe I'm just confused. :-)
+Pie Number of slices to send: Send
I just thought of a major flaw of using (just) a BitSet or boolean[] - you don't preserve the ordering of chars. That's why I initially suggested a LinkedHashSet instead of a HashSet or TreeSet.
+Pie Number of slices to send: Send
 

Jeff Verdegan wrote:Actually, I think it's the size of an int, so 256k...


Actually, according to this blog (admittedly old), it's size isn't defined (and I couldn't see any reference to it in the JLS). Further down, someone seems to reckon it is the same size as a byte. This one suggests (as you said) that it actually uses different sizes for single values and arrays.

So, who knows? Anyway, 64/256/1024, it's all peanuts these days. God, I feel old.

Winston
+Pie Number of slices to send: Send
 

Rob Spoor wrote:I just thought of a major flaw of using (just) a BitSet or boolean[] - you don't preserve the ordering of chars.


Not really necessary surely? The ordering is implicit in the original array. My assumption is that the method would be something like:
public static final char[] removeDups(char[] chars) {...
and you're only usiing the array/BitSet to work out whether you've got a duplicate or not.

Winston
+Pie Number of slices to send: Send
 

Winston Gutkowski wrote:

Rob Spoor wrote:I just thought of a major flaw of using (just) a BitSet or boolean[] - you don't preserve the ordering of chars.


Not really necessary surely?



Depends on the OP's requirements, which I don't believe he made clear in this regard. For a real-world case I wouldn't expect ordering to matter, but for homework, I wouldn't be at all surprised if that constraint were present.
+Pie Number of slices to send: Send
 

Jeff Verdegan wrote:

Winston Gutkowski wrote:

Rob Spoor wrote:I just thought of a major flaw of using (just) a BitSet or boolean[] - you don't preserve the ordering of chars.


Not really necessary surely?



Depends on the OP's requirements, which I don't believe he made clear in this regard. For a real-world case I wouldn't expect ordering to matter, but for homework, I wouldn't be at all surprised if that constraint were present.


Not only that; it strikes me as highly likely that working out the logic which filters out duplicates is the point of the exercise, rather than finding the Java API that does it for us.
+Pie Number of slices to send: Send
 

Dennis Deems wrote:Not only that; it strikes me as highly likely that working out the logic which filters out duplicates is the point of the exercise, rather than finding the Java API that does it for us.


Probably; which is why all we've offered is suggestions that might aid the process. Indeed, a boolean[] doesn't involve an API at all.

Winston
+Pie Number of slices to send: Send
 

Winston Gutkowski wrote:

Dennis Deems wrote:Not only that; it strikes me as highly likely that working out the logic which filters out duplicates is the point of the exercise, rather than finding the Java API that does it for us.


Probably; which is why all we've offered is suggestions that might aid the process. Indeed, a boolean[] doesn't involve an API at all.

Winston


I'm not sure whom you mean when you say "we", but I really thought I saw the idea of using a LinkedHashSet discussed here.
+Pie Number of slices to send: Send
 

Dennis Deems wrote:I'm not sure whom you mean when you say "we", but I really thought I saw the idea of using a LinkedHashSet discussed here...


I mean all of us who've offered advice. In this case, I think that a LinkedHashSet might be a bit OTT, but I say again that that all we have done is offer aids to the solution. How Raj decides to use them (or not) is up to him.

Winston

This tiny ad will self destruct in five seconds.
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com


reply
reply
This thread has been viewed 2597 times.
Similar Threads
Find common elements in 3 int array
Big O notation question
c++ code not compiling in online compiler?
Analyzing time complexity of k-way merge operation for merge sort
removing a character from string
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 09:25:51.