This week's book giveaway is in the Mac OS forum.
We're giving away four copies of a choice of "Take Control of Upgrading to Yosemite" or "Take Control of Automating Your Mac" and have Joe Kissell on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes compare two arraylists and get position of common elements Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Beginning Java
Bookmark "compare two arraylists and get position of common elements" Watch "compare two arraylists and get position of common elements" New topic
Author

compare two arraylists and get position of common elements

Sergio Sa
Greenhorn

Joined: Mar 07, 2012
Posts: 2
I have two arraylists and the second one is a subset of the first.
I want to know the initial and final position in the first arraylist of elements in the subset (in my example the position in arrayList of: uno, due, tre)

How to modify this code?

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7892
    
  21

Sergio Sa wrote:I want to know the initial and final position in the first arraylist of elements in the subset (in my example the position in arrayList of: uno, due, tre)
How to modify this code?

Well first, ShowSomeEffort (←click). What have you tried?

One tip for you: You say that you "want to know the initial and final position in the first arraylist of elements in the subset", yet your loops don't suggest that that's what you're doing. How do you think you might want to change them?

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Here is my Algorithm:

1. scan the Higher Length ArrayList

2. put the element index into Hashtable as key = element and value = position(negate the index)

3. scan through 2nd List , If you find the same element Hashtable already mark the element value/index of the element as positive from negative

4. now scan the Hashtable values which is positive and find the first index and last index.

time complexity will be approximately O(n) though...[scaning first list O(n)+2nd List O(n)+build hash table O(n)+ hash function O(1)+scanning hashtable O(n) => O(n)]

you can modify the algorithm which ever way you like ...

If you go for brute force method as using 2 nested for loop then time complexity will be O(n power of 2).

Note: Correct me If I am Wrong
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Welcome to JavaRanch Sergio Sa
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7892
    
  21

Seetharaman Venkatasamy wrote:1. scan the Higher Length ArrayList

Fine so far.

2. put the element index into Hashtable as key = element and value = position(negate the index)
3. scan through 2nd List , If you find the same element Hashtable already mark the element value/index of the element as positive from negative
4. now scan the Hashtable values which is positive and find the first index and last index.

Overly complex. Also, changing keys in collections is not usually a good idea (and in a Hashtable may be disastrous).

time complexity will be approximately O(n) though...[scaning first list O(n)+2nd List O(n)+build hash table O(n)+ hash function O(1)+scanning hashtable O(n) => O(n)]

Ah, you never said you were looking for the fastest algorithm, just an algorithm.

you can modify the algorithm which ever way you like ...

No you can't.

My advice: Keep it simple, and look at the problem as you originally stated it. You are looking for the first and last position; all that storing of elements is just a red herring (and actually unnecessary).

Give it another try; if you still have issues, come back.

Winston

[Edit] Ooops. Thought you were OP. My comments still stand though.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Winston Gutkowski wrote:
2. put the element index into Hashtable as key = element and value = position(negate the index)
3. scan through 2nd List , If you find the same element Hashtable already mark the element value/index of the element as positive from negative
4. now scan the Hashtable values which is positive and find the first index and last index.

Overly complex. Also, changing keys in collections is not usually a good idea (and in a Hashtable may be disastrous).

since both array has an unique(means same Objects) object, I dont see any complex here. I didnt talk about changing keys
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7892
    
  21

Seetharaman Venkatasamy wrote:since both array has an unique(means same Objects) object, I dont see any complex here. I didnt talk about changing keys

Then what's the business about "If you find the same element Hashtable already mark the element value/index of the element as positive from negative"?

I agree that if speed is an overriding concern and the lists are big, it might be worth loading one of them into a hashed collection (although I'd use a HashMap or HashSet myself), but the fact is that you don't need to do it.

[Edit] Another consideration: What if the Lists contain duplicate elements; how should they be matched? Sergio hasn't said, but a HashMap will not allow duplicates.

Winston
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Winston Gutkowski wrote:
Then what's the business about "If you find the same element Hashtable already mark the element value/index of the element as positive from negative"?

Might be, I didnt explain it well. what I was saying is that find the entry using key (which is element) and its value is -index. and make it possitive.

Winston Gutkowski wrote:
[Edit] Another consideration: What if the Lists contain duplicate elements; how should they be matched? Sergio hasn't said, but a HashMap will not allow duplicates.
Winston

<edit>
Yeah, this may be bit complex. when I go my home back . definitely post the solution
</edit>


Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7892
    
  21

Seetharaman Venkatasamy wrote:Yeah, this may be bit complex. when I go my home back . definitely post the solution

Could I suggest that you do it in a different thread then? The idea here is to guide people to a solution, not hand it to them; and Sergio still hasn't come up with any ideas of his own yet.

Winston
Sergio Sa
Greenhorn

Joined: Mar 07, 2012
Posts: 2
I have resolved with this code:

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7892
    
  21

Sergio Sa wrote:I have resolved with this code:

Seems reasonable. It's worth noting that most "sublist" methods make the 'endIndex' value exclusive though.

Winston
 
GeeCON Prague 2014
 
subject: compare two arraylists and get position of common elements