java - 有效地测试数组成员资格

Question

这个问题已经有答案了:

Efficient algorithm to determine if two sets of numbers are disjoint (4 个回答)

已关闭 8 年前。

在一次 Java 开发人员采访中，我被问到了这个问题:

Given two arrays of integers, print out the values from the first array which are not present in the second array. The total time complexity should be O(n).

我提出的方法是:

1. 使用哈希表存储第二个数组的值。
2. 现在检查第一个数组的值是否存在于哈希表中。如果没有，则打印这些值。

还有其他更有效的方法来实现这一点吗？

Answer 1

我们假设两个数组的长度大致相同，因此使用 n 来描述两个数组的长度。 (否则我们需要引入一个新变量。)

替代方案概述:

线性搜索:如果我们将第二个数组存储为未排序的数组/列表，则每次搜索需要 O(n) 时间，并且总时间为O(n²)。

二分搜索:如果我们对第二个数组进行排序，则需要 O(n log n) 时间。每个查询需要 O(log n) 时间，总共 O(n log n )时间。

平衡树:如果我们将第二个数组存储在 TreeSet 中，则每次搜索需要 O(log n>) 时间，总共 O(n log n) 时间。

哈希表:如果我们像您提到的那样将第二个数组存储在 HashSet 中，则每次插入都需要 O(1) 摊销时间，并且每次搜索需要 O(1) 时间，总共需要 O(n) 时间。

位 vector :如果我们创建一个 2³² 元素的位 vector 来覆盖所有可能的 Java int 或 Integer 值，我们可以将第二个数组的每个元素相加，并在 O(1) 时间内测试某个值是否存在，总共 O(O(O) >n) 所需的时间。然而，对于 2³² 元素的初始化，有一个非常昂贵的常数项。

下限参数:第二个数组的长度为 O(n)。如果我们没有扫描整个数组，就不可能准确判断某个值是否在第二个数组中。因此解决这个问题的绝对最短时间是Ω(n)。这意味着 O(n) 是我们能做的最好的事情。