• Post Reply Bookmark Topic Watch Topic
  • New Topic

Finding the intersection and union in two sorted Lists  RSS feed

 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is an assignment that I've been doing and the specifications for it are that I need to implement two methods(intersection and union) using the comparable interface(only allowed to use Java Collection API basic methods) and explain their complexity.

I've finished the first part(creating the intersection method) and described it's complexity.

The way I did it was by using a binary search on the second sort list while using a for loop for the first list so I can traverse through the first list and second list in one go. If I find a match in both sorted lists, then I add them to a list that contains all objects that are distinct and are the intersection of List 1 and List 2.

In essence, the time complexity for my method is nlogn. the n is for the for loop through the first list. The logn is because of the binary search. I don't know if it possible to make it a little bit better.



I notice that my previous code didn't check for duplicates. What I added is a variable previous that keeps track of the previous element that was found. Why I think this works is because we have a sorted list. We can have a sorted list that have duplicates like this {6, 6, 6} but not a list like this {4, 6, 4}. What this means is that the duplicate has to always be behind the element that was found previously given by the rule that we have a sorted list which or may not contain duplicates.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You could make it a little better, although I think it is still nlogn.
Suppose your lists are A and B, and that the first element of A
equals the nth element of B. Then for the second element of A,
you only need to look at B, starting from position n + 1 (or n,
depending how you handle duplicates).
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've changed the intersection to look like this



Suppose if we have these sorted lists

A = {1, 2, 6, 9, 9}
B = {1, 2, 9 12}

For these two lists I would have to do four binary searches instead of five. The previous code did 5 anyways even though there is no point because you have a duplicate.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!