如何与大数的数组进行比较？

Question

我有200个排序的正整数数组（其中一些数字超过一百万）。我需要找到每个数组中存在的第一个数字。你会建议什么？

Answer 1

• 保留每个阵列的索引。
• 从第一个数组的第一个数字开始，作为参考。
• 是第n个数组的第一个数字低于参考，增加其索引。
• 是第n个数组的第一个数字等于参考，增加n并继续 - 下一个数组。
• 是第n个数组的第一个数字高于参考，使用该数字作为参考并重新开始。
• 如果n == 201，则您的引用存在于每个数组中。

编辑：一个代码示例：

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

您可以对阵列执行k-way合并，并检查出现k次的第一个元素。

另一种方法是创建一个histogram，并选择在直方图中出现k时间的第一个元素。在Java中的直方图可以很容易地通过一个Map<Element,Integer>

来实现两种解决方案都O(kn)其中k是阵列的数量和n是阵列的平均尺寸，因此它是在输入的大小基本上是线性的。