How And And a large number of arrays of numbers?

Question

I have 200 arrays of sorted positive integers (some of them have more than a million numbers). I need to find the first number that exists in each array. What would you suggest?

Answer 1

• Keep an index for each array.
• Start with the first of the first array as a reference.
• Is the first number of the nth array lower than the link, increases its index.
• Whether the first number of the nth array is equal to the reference, increment n and continue - the next array.
• Is the first number of the nth array higher than the link, use this number as a link and start with.
• If n == 201, your link exists in every array.

Edit: sample code:

while n < len(data): item = data[n][indices[n]] if item < reference: indices[n] += 1 elif item == reference: n += 1 elif item > reference: reference = item n = 0 print reference 

Answer 2

You can merge k-way on arrays and check the first element that appears k times.

An alternative is to create a histogram and select the first element that displays the time k on the histogram. A histogram in java can be easily implemented using Map<Element,Integer>

Both solutions: O(kn) , where k is the number of arrays and n is the average size of the array, so it is mostly linear in input size.