Java - matching two unordered lists

Question

I have the following problem: I need to find pairs of identical elements in two lists that are unordered. The point in these two lists is that they are "approximately equal" - only some elements are shifted by several indices, for example. (Note, these objects are not ints, I just use integers in this example):

[1,2,3,5,4,8,6,7,10,9] [1,2,3,4,5,6,7,8,9,10] 

My first attempt was to iterate over both lists and generate two HashMaps based on some unique key for each object. Then, from the second pass, I just pulled out the elements from both cards. This gives O(2N) in space and time.

I was thinking of a different approach: we will point to pointers to the current element in both lists, as well as to the current set for each list. pseudocode will look like this:

 while(elements to process) elem1 = list1.get(index1) elem2 = list2.get(index2) if(elem1 == elem2){ //do work ... index1++; index2++; } else{ //Move index of the list that has no unamtched elems if(firstListUnmatched.size() ==0){ //Didn't find it also in the other list so we save for later if(secondListUnamtched.remove(elem1) != true) firstListUnmatched.insert(elem1) index1++ } else { // same but with other index} } 

The above probably does not work ... I just wanted to get a general idea of ​​what you think of this approach. Basically, it supports a hash on the side of each list whose size is <size problem. This should be ~ O (N) for a small number of non-local elements and for small "gaps". Anyway, I look forward to your answers.

EDIT: I can't just return the intersection set of two lists of objects, since I need to perform operations (even multiple operations) for the objects that I find as a match / mismatch

Answer 1

I cannot just return the intersection set of two lists of objects, since I need to perform operations (even several operations) for objects that I find as a match / mismatch

You can maintain a set of objects that do not match. This will be O (M) in space, where M is the largest number of replaced elements at any point. This will be O (N) for the time, where N is the number of elements.

 interface Listener<T> { void matched(T t1); void onlyIn1(T t1); void onlyIn2(T t2); } public static <T> void compare(List<T> list1, List<T> list2, Listener<T> tListener) { Set<T> onlyIn1 = new HashSet<T>(); Set<T> onlyIn2 = new HashSet<T>(); for (int i = 0; i < list1.size(); i++) { T t1 = list1.get(i); T t2 = list2.get(i); if (t1.equals(t2)) { tListener.matched(t1); continue; } if (onlyIn2.remove(t1)) tListener.matched(t1); else onlyIn1.add(t1); if (!onlyIn1.remove(t2)) onlyIn2.add(t2); } for (T t1 : onlyIn1) tListener.onlyIn1(t1); for (T t2 : onlyIn2) tListener.onlyIn2(t2); } 

Answer 2

If I understand your question correctly, you can use Collection.retainAll and then iterate over the collection that was saved and do what you have to do.

 list2.retainAll(list1); 

Answer 3

All map-based approaches will at best be O (n log (n)), since creating a map is sorting an insert. The effect is to make the insertion sort for both and then compare them, which is as good as getting.

If the lists start with sorting, the sorting step should not take as much time as the average case, and will be scaled using O (n log (n)), so just sort by both and compare. This allows you to perform operations and perform operations on elements that match or don't match accordingly.