多个数组求交集
难度:
标签:
题目描述
代码结果
运行时间: 24 ms, 内存: 16.3 MB
/*
* 思路:
* 1. 使用Java Stream API,首先将第一个数组转换为Set集合。
* 2. 然后对剩余的每个数组使用流操作,过滤出出现在每个数组中的元素。
* 3. 最后将结果转换为List并排序。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public List<Integer> intersection(int[][] nums) {
Set<Integer> result = Arrays.stream(nums[0]).boxed().collect(Collectors.toSet());
result.retainAll(Arrays.stream(nums)
.skip(1)
.map(array -> Arrays.stream(array).boxed().collect(Collectors.toSet()))
.reduce(result, (a, b) -> { a.retainAll(b); return a; }));
return result.stream().sorted().collect(Collectors.toList());
}
}
解释
方法:
此题解方法首先确认输入数组是否为空或null,如果满足上述任一条件,直接返回空数组。如果数组只包含一个子数组,直接返回该数组(题目已保证子数组内元素不重复且已排序)。接下来,算法以第一个子数组初始化一个集合作为交集的基础,然后遍历剩余的子数组,利用集合的intersection方法来更新交集。最后,将得到的交集集合转换为列表,并进行排序(虽然题目中子数组已排序,但集合操作后元素顺序可能改变),然后返回排序后的列表。
时间复杂度:
O(n + m log m)
空间复杂度:
O(m)
代码细节讲解
🦆
题解中提到,如果输入数组为空或null时,直接返回空数组。这种情况下,对于输入为多个空子数组的情况(例如`nums = [[]]`或`nums = [[], [], []]`),返回结果是否也应该是空数组,还是应该有所区别?
▷🦆
题解中的算法在每次遍历子数组时使用`set`的`intersection`方法来更新交集。为什么选择使用集合(set)来处理交集而不是使用其他数据结构如列表(list)?
▷🦆
算法描述中指出,最后一步是将交集的集合转换为列表并进行排序。既然输入的子数组已经是排序的,能否在交集的更新过程中保持元素的有序状态,从而避免最后的排序操作?
▷🦆
在题解的代码中,对于只有一个子数组的情况,直接返回了这个子数组。这种实现是否完全符合题目要求的返回格式,尤其是考虑到题目要求返回的数组元素在所有数组中都出现过?
▷