如何对大量数字数组进行AND操作？

Question

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

- yegor256

---

抱歉，此评论已被删除。 - cl-r

方法 Arrays.binarySearch() - Edwin Dalorzo

比“AND”更合适的描述可能是“交集”。 - Sjoerd

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

- Sjoerd

Answer 2

您可以对数组执行k路合并，并检查出现k次的第一个元素。

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

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

- amit