permaculture playing cards*
The moose likes Programming Diversions and the fly likes Find repreating character in an array Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Find repreating character in an array" Watch "Find repreating character in an array" New topic
Author

Find repreating character in an array

Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

finds the index of the first repeating character in an array, by iterating through the array only once.

I implemented this as per the code given. Is there any other efficient way to do it?

>


My Blog SCJP 5 SCWCD 5
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11150
    
  16

I think your idea is solid, although I may not have used a tree.

Basically, you have to remember every character you've encountered as you parse, then check each new one.

If we're simply talking about characters, I might just use an array of 256 ints. read a character, use it's ascii value as the index into the array. if the value there is 0, i have not encountered it, so I set the value to 1. If the value is 1, i've encountered it, so I'm done.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

Thanks Fred for the reply. []
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

Himanshu Gupta wrote:finds the index of the first repeating character in an array, by iterating through the array only once.

I implemented this as per the code given. Is there any other efficient way to do it?

>


This will not work when we have an array like {'h','y','d','h'}
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

This code is working fine for the given question.

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11150
    
  16

pseudocode:


From the Sun Javadocs:
char: The char data type is a single 16-bit Unicode character. It has a minimum value of '\u0000' (or 0) and a maximum value of '\uffff' (or 65,535 inclusive).


Note - my pseudocode is untested and not carefully thought out, but I think it would work.
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

Thanks once again Fred. Do you see any problem in the code given by me. Just asking for your help if in case I have missed something.

Adam Michalik
Ranch Hand

Joined: Feb 18, 2008
Posts: 128
Himanshu, both your solutions are literally fine (they do not iterate over the array) but they have a hidden iteration in the other data structures - the TreeSet.add() and ArrayList.contains() method both perform iteration to look for the given element. The TreeSet.add() takes O(log n) time, the ArrayList.contains() takes O(n). So using an ArrayList is no better than iterating over the given char array - it's just as if you were copying it and iterating over the char[] copy. The TreeSet solution is nice and fast (fastest possible in the general case of object repetition), though Fred's solution is fastest possible in the bounded by character's values case. See Wikipedia.
Adam Michalik
Ranch Hand

Joined: Feb 18, 2008
Posts: 128
---
(double submit, sorry)
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

Thanks Adam. Wonderful answers.

The question is described here.

[i]
Write a method that finds the index of the first repeating character in an array, by iterating through the array only once. If there is no repeating character, the method should return -1.

You are not allowed to use a inner loop like

because that would iterate through the array more than once.
(Hint: Data structures from the Collections framework can be used to avoid a nested loop)



[/i]
>
Adam Michalik
Ranch Hand

Joined: Feb 18, 2008
Posts: 128
Judging from the hint, I'd say that the solution with set is the most suitable - fulfils the task's requirements, is fast enough and memory -optimal. You may consider using HashSet instead of a TheeSet initialized to the array's capacity - the add() operation will be even faster. The solution with the int array is smart, but for small char arrays a lot of memory will be wasted.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Find repreating character in an array
 
Similar Threads
Sort the Array in reverse order
basic use of generic arrays
Doubt in Array
Displaying data in Two Columns
exceptions and type casting confusion