Feb 17, 2008

Finding repeated numbers in two arrays

Given two sorted integer arrays (array size may differ).

Find the number of values that appear in both arrays.

For example, given:

A: 1, 3, 5, 8, 10. 14, 16, 25, 28, 47
B: 2, 4, 7, 8, 11, 12, 14, 17, 47, 56, 64

The result should be 3, since value 8, 14, 47 appear in both array.

Hint: A simple approach would take O(m+n) however it can be done in O(nlogm) (a better bound if n is very small as compared to m)

No comments: