File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

compare two arraylists and get position of common elements

 
Sergio Sa
Greenhorn
Posts: 2
  • 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9477
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Java Windows XP
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to JavaRanch Sergio Sa
 
Winston Gutkowski
Bartender
Pie
Posts: 9477
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9477
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9477
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 2
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have resolved with this code:

 
Winston Gutkowski
Bartender
Pie
Posts: 9477
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic