java - 如何与大量的数字数组？

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 路合并并检查出现k次数的第一个元素。

另一种方法是创建一个直方图，并选择直方图中出现k时间的第一个元素。java中的直方图可以通过以下方式轻松实现Map<Element,Integer>

两种解决方案都是数组O(kn)的k数量和数组n的平均大小，因此它在输入的大小上基本上是线性的。