Java 程序高效查找两个数组的交集

"Java 程序查找两个数组之间的共同元素" 在 Java 编程中，有时我们需要找出两个数组之间的公共元素，这是一项常见的任务。本资源主要探讨了两种不同的方法来解决这个问题：一种是使用迭代，另一种是利用哈希集。 1. **迭代方法**： 这种方法通过遍历两个数组并比较元素来找到公共元素。首先，我们获取两个数组，然后逐个检查数组1中的元素是否也在数组2中出现。如果找到匹配项，我们将它添加到结果集合中，以确保没有重复。这种方法的时间复杂度是 O(n^2)，因为我们需要对每个数组的每个元素进行比较。辅助空间取决于结果集合的大小，可能达到 O(n)。 ```java for (int i = 0; i < array1.length; i++) { for (int j = 0; j < array2.length; j++) { if (array1[i].equals(array2[j])) { commonElements.add(array1[i]); } } } ``` 2. **使用哈希集（HashSet）**： 哈希集提供了一种更高效的方法来查找公共元素，特别是当处理大型数据时。我们首先将两个数组的元素分别添加到两个哈希集中。然后，使用 `retainAll()` 方法，这个方法会保留哈希集1中同时存在于哈希集2的元素，从而得到公共元素。这种方法的时间复杂度降低到了 O(n)，因为它只需要遍历一次较短的数组。辅助空间同样为 O(n)，因为我们需要创建两个哈希集。 ```java Set<String> set1 = new HashSet<>(Arrays.asList(array1)); set1.retainAll(new HashSet<>(Arrays.asList(array2))); commonElements.addAll(set1); ``` 3. **另一种哈希集方法**： 这个方法使用一个哈希集来存储第一个数组的元素，然后遍历第二个数组，检查每个元素是否在哈希集中存在。如果存在，就将元素添加到结果数组中。这种方法同样具有 O(n) 的时间复杂度和 O(n) 的辅助空间。 ```java Set<String> set = new HashSet<>(Arrays.asList(array1)); for (String element : array2) { if (set.contains(element)) { commonElements.add(element); } } ``` 以上就是查找两个数组之间公共元素的两种常见 Java 实现。在选择方法时，应考虑性能需求和可用内存，特别是在处理大量数据时。使用哈希集通常会提供更好的性能，特别是当数组元素无序且不需要保持原始顺序时。