Intersection of Arrays with Distinct Element in Java

在 Java 中查找具有唯一元素的数组的交集，涉及识别两个或多个数组之间共享的公共元素。由于每个数组中的元素都是唯一的，因此任务简化为有效地比较集合。此过程在数据过滤、集合操作和以编程方式解决数学问题等各种应用中非常有用。

输入

数组 1 [3, 5, 7, 9]

数组 2 [5, 9, 11, 13]

输出

交集 [5, 9]

解释

输出显示了两个数组的交集，即两者中存在的公共元素。在此示例中，5 和 9 出现在 数组 1 和数组 2 中。因此，这两个数组的交集是 [5, 9]，代表它们之间的共享元素。

方法 1：使用 HashSet 进行交集计算

算法

步骤 1：初始化 HashSet：HashSet 是理想的选择，因为它能确保常数时间内的元素存在性查找。此外，它会自动防止重复值，从而高效地存储唯一元素，为与第二个数组进行比较做好准备。

步骤 2：添加第一个数组的元素：遍历第一个数组，并将每个元素添加到 HashSet 中。此步骤确保数组中的所有元素都以唯一的方式存储。通过将元素添加到 HashSet，我们可以在与第二个数组的元素进行比较时实现快速查找，从而提高交集过程的效率。

步骤 2.1：遍历第一个数组：在此步骤中，循环遍历第一个数组的每个元素。对于每个元素，将其添加到 HashSet 中。这确保第一个数组中的所有元素都存储在 HashSet 中，从而在与第二个数组的元素进行比较时实现高效查找。

步骤 3：检查第二个数组以查找公共元素：遍历第二个数组，并检查每个元素是否存在于 HashSet 中。此步骤确定元素是否是两个数组之间的公共元素。如果在 HashSet 中找到该元素，则表示它也存在于第一个数组中，表明匹配。

步骤 3.1：检查第二个数组的每个元素：在此步骤中，循环遍历第二个数组的每个元素。对于每个元素，检查它是否存在于 HashSet 中。此检查有助于识别两个数组之间的公共元素。如果在 HashSet 中找到该元素，则表示匹配，应将其存储在结果中。

步骤 4：存储交集元素：如果第二个数组中的某个元素存在于 HashSet 中，则将其识别为公共元素。将此元素添加到结果列表或集合中以存储交集。此步骤收集所有匹配的元素，确保结果中只包含两个数组之间的公共元素。

步骤 4.1：处理重复项：如果需要，确保结果列表或集合仅包含唯一元素。虽然 HashSet 在比较过程中会自动处理重复项，但如果使用列表，可以应用逻辑来避免添加重复的交集元素。此步骤可确保结果准确地反映唯一的公共元素。

步骤 5：输出结果：遍历完成后，结果列表将包含在两个数组之间找到的所有公共元素。该列表代表数组的交集。最后，输出此列表，向用户提供两个数组共享的公共元素。

步骤 6：返回或显示交集：输出结果后，下一步是向用户返回或显示交集。根据应用程序，您可以将交集作为结果返回，将其打印到控制台，或将其用于进一步处理。最后一步确保交集可用于使用。

让我们在 Java 程序中实现上述步骤。

文件名：ArrayIntersection.java

输出

 
Intersection: [5, 9]   

复杂度分析

时间复杂度

此方法的 time complexity 为 O(m + n)，其中 m 是第一个数组的长度，n 是第二个数组的长度。将元素添加到 HashSet 的平均时间复杂度为 O(1)，检查第二个数组中的公共元素对于每个组件也为 O(1)。

空间复杂度

此方法的 space complexity 为 O(m)，其中 m 是第一个数组的长度。这是因为 HashSet 存储了第一个数组中的所有唯一元素。结果列表使用的空间为 O(k)，其中 k 是找到的公共元素的数量。

方法 2：使用排序和双指针

算法

步骤 1：对两个数组进行排序：首先，将两个数组按升序排序。排序会组织元素，从而更容易按顺序比较相应元素。排序使我们能够通过线性遍历数组来有效地处理比较。

步骤 1.1：单独对每个数组进行排序：首先，独立地将两个数组按升序排序。排序可确保每个数组中的元素按顺序排列，这使得通过在遍历期间进行线性比较来查找公共元素的过程更加简单。

步骤 2：初始化两个指针：使用两个指针，每个数组一个

• 指针 i 指向第一个数组的开头。
• 指针 j 指向第二个数组的开头。

这些指针将遍历数组，并通过比较它们指向的值来帮助识别公共元素。

步骤 3：遍历两个数组：使用循环同时遍历数组，同时两个指针都在边界内（即，没有一个指针超出其各自数组的长度）。在每一步，比较指针 i（在第一个数组中）和指针 j（在第二个数组中）指向的值。

步骤 3.1：在遍历期间处理每次比较

在遍历两个数组时，比较两个指针指向的元素。在每一步：如果元素相等，则将元素添加到结果列表，并向前移动两个指针。

如果第一个数组中的元素较小，则增加第一个数组的指针。

否则，增加第二个数组的指针。

步骤 4：比较元素并移动指针：每次比较有三种可能的情况

情况 1：元素相等

如果第一个数组中 i 指向的元素等于第二个数组中 j 指向的元素。将此元素添加到结果列表中，因为它是一个公共元素。

向前移动两个指针（增加 i 和 j），以继续比较两个数组中的下一个元素。

情况 2：第一个数组中的元素较小：如果第一个数组中 i 指向的元素小于第二个数组中 j 指向的元素

向前移动指针 i，以在第一个数组中检查下一个较大的元素。这是因为在排序顺序中，较小的元素无法匹配较大的元素。

情况 3：第二个数组中的元素较小

如果第二个数组中 j 指向的元素小于第一个数组中 i 指向的元素

向前移动指针 j，以在第二个数组中检查下一个较大的元素。

同样，第二个数组中的较小元素也无法匹配第一个数组中的较大元素。

步骤 5：重复直到一个指针到达末尾：继续比较过程，直到一个指针到达其各自数组的末尾。此时，所有可能的公共元素都将被识别并存储在结果列表中。

步骤 5.1：确保处理所有公共元素：继续遍历，直到一个指针到达其各自数组的末尾。此时，所有可能的公共元素都将被识别并添加到结果列表中。由于一个数组已完全遍历，因此不再需要进一步的比较。

步骤 6：返回结果：遍历完成后，结果列表将包含两个数组共享的所有公共元素。将此列表作为两个数组的最终交集返回或显示。

让我们在 Java 程序中实现上述步骤。

文件名：ArrayIntersection.java

输出

 
Intersection: [5, 9]   

复杂度分析

时间复杂度

该程序的 time complexity 为 O(m log m + n log n + min(m, n))。对两个数组进行排序分别需要 O(m log m) 和 O(n log n) 的时间。排序后，用于查找公共元素的三指针遍历运行时间为 O(min(m, n))，从而使该方法总体上高效。

空间复杂度

该程序的 space complexity 为 O(1)，因为它不需要额外的 数据结构 来进行处理。交集是使用排序数组和双指针原地计算的。仅使用最小的额外空间用于 变量，与依赖于 HashSet 或列表的方法相比，此方法在空间效率方面具有优势。