It depends a bit on what you mean by "common element." If you mean a symbol that occurs in each list, Joachim's suggestions are good. If an element can also be a subsequence, then your question is a slight generalization of the well-known longest common subsequence problem, for which there are many solutions, cf the wikipedia entry for this problem linked below.
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
Joachim's proposal is nice, but as far as I know, using hash-tables will not result in O(n) worst-case behavior, instead it will result in O(n^2) worst-case behavior as both searching and inserting is O(n) in worst-case for hash-tables (it's O(1) only on average). As for the first solution, notice that the sequences must contain "comparable" objects, so that they can be sorted.
If the elements in your sequences cannot be compared (other than for equality), then it seems that you'll have an O(min(m,n)^2) worst-case complexity where m and n is the size of the first and second sequence respectively.
Of course, you have two very different problems depending on whether your Alphabet (possible elements of the sequence) is fixed and known beforehand, or whether it is unknown and unbounded. In the former case, time n+m suffices: just determine which if the symbols occur in each sequence and check whether the intersection of the two sets is non-empty.
Thank you all for the answers and discussion. I am not good at arguing the exact time complexity of different implementations. I just want to make the question more clear:
The two sequences are of length n with the alphabet set from 1 to 2n.
1. only determine if there is a common number in two sequences and record their respective indices in two sequences, stop the comparison once one common number is found;
2. find all common numbers and record respective indices for each one.
thanks
For 1. I suggest
a) sort both list (there exist very fast implemented functions for this in most programming environments)
b) compare the smallest elements from both. If they are equal you are done; otherwise remove the smaller one from its list and repeat until the lists are empty.
Adaption for 2: Convert the sequences to sequences of pairs (i,pos) where i is the original element and pos is its position, Sort these according to i.
Then compare the two lists as above, but if there is a match, continue. You get the indices from the pos variables when the two elements are equal.
Sorting takes n log n time, then only 2n more comparisons are needed. Note that there could be n^2 many solutions (if all elements are equal). If you want at least one index pair for every number that occurs in both the solution above works. If you want all of them, then you need to record some obvious things during the list comparison.
Thank you all for the answers. Sounds Patrice's implementation is very simple and take only linear time if I understand correctly. In this algorithm, sorting is not needed, just scam each sequence and generate a list of length 2n for each, and finally check the resulting lists.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics