Suppose I have two lists of N 3 by 3 vectors of integers.
I need to find a quick way (say of running time at most N^(1+epsilon)) to find the vectors of the first list that have the same 1st coordinate with a vector of the second list.
Of course, I could do the following naive copmarison:
for u in list_1 do
for v in list_2
if u[1] equals v[1] then
print u;print v;
end if;end for; end for;
This, however, would require N^2 loops.
I feel that sorting the two lists according to their first coordinate and then look up for collisions is perhaps a fast way. Bubbleshort, etc., would probably take logN time, but I can't really see how to code the search for collision between the sorted lists.
Any help would be appreciated.
O(n)
without using hash tables, sets or any other data structures that are not simple arrays or linked lists. The fact that the lists are sorted helps you - inside of a while loop (not for loop) you would move a pointer to left list and a right list conditionally. The exact details can be somewhat messy, but because both lists are sorted, you only need to traverse each one once, going in one direction only. In fact, you do not need to be able to access them by index at all. The step is similar to a merge step of the merge sort algorithm.