leetcode
leetcode 1951 ~ 2000
多个数组求交集

多个数组求交集

难度:

标签:

题目描述

代码结果

运行时间: 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)?
使用集合(set)来处理交集而不使用列表(list)的主要原因是效率。集合在Python中是基于哈希表实现的,因此查找、插入和删除操作的平均时间复杂度为O(1)。使用集合的`intersection`方法来计算交集特别高效,因为它可以快速检查和比对元素是否存在于其他集合中。而相对地,如果使用列表,检查一个元素是否存在于列表中需要O(n)的时间复杂度,这会使得整体算法效率降低,特别是在处理大量数据时更为明显。
🦆
算法描述中指出,最后一步是将交集的集合转换为列表并进行排序。既然输入的子数组已经是排序的,能否在交集的更新过程中保持元素的有序状态,从而避免最后的排序操作?
虽然输入的子数组是排序的,但在使用集合进行交集操作时,集合内部的元素顺序是不确定的,因为集合是无序的数据结构。尽管可以考虑使用有序数据结构(如有序集合或在列表中维护有序状态)来避免最后的排序操作,但这通常会牺牲一些性能,因为维护元素的有序状态(特别是在交集操作中)可能比简单地在最后进行排序更复杂或更耗时。因此,在效率和简单性的权衡下,选择在最后对结果列表进行排序是一个实用的解决方案。
🦆
在题解的代码中,对于只有一个子数组的情况,直接返回了这个子数组。这种实现是否完全符合题目要求的返回格式,尤其是考虑到题目要求返回的数组元素在所有数组中都出现过?
对于只有一个子数组的情况,直接返回这个子数组是符合题目要求的。因为当只存在一个子数组时,该子数组的所有元素自然是出现在所有(即唯一一个)子数组中的。因此,这种实现完全符合题目要求的返回格式,即返回一个包含所有在给定子数组中共同出现的元素的数组。

相关问题