java - 大型整数集的搜索和差异

Question

我有 2 个大整数数组。我必须了解这些数组的区别(即第二个数组中的元素，而不是第一个数组中的元素，反之亦然)。我正在实现线性搜索并将差异存储在数组中。有什么方法可以更快(线性时间)？

Answer 1

如果将一个数组放入一个散列集中，然后遍历另一个数组，探测散列集，则很容易获得 O(n+m) 时间。当然，如果您的数组已排序，那么您可以直接拥有 O(n+m)。