leetcode
leetcode 1801 ~ 1850
至少在两个数组中出现的值

至少在两个数组中出现的值

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.1 MB


/*
 * 思路:
 * 1. 使用流处理集合,计算每个元素在多个数组中的出现次数。
 * 2. 过滤出现次数大于1的元素,最终转换为列表。
 */
import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        Map<Integer, Integer> countMap = new HashMap<>();

        // 统计每个数字出现的数组个数
        Arrays.stream(nums1).distinct().forEach(num -> countMap.put(num, countMap.getOrDefault(num, 0) + 1));
        Arrays.stream(nums2).distinct().forEach(num -> countMap.put(num, countMap.getOrDefault(num, 0) + 1));
        Arrays.stream(nums3).distinct().forEach(num -> countMap.put(num, countMap.getOrDefault(num, 0) + 1));

        // 过滤出出现次数大于1的数字
        return countMap.entrySet().stream()
                .filter(entry -> entry.getValue() > 1)
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
    }
}

解释

方法:

该题解首先将每个数组转换为一个集合,以消除重复元素并便于后续操作。接着,计算这三个集合间任意两个集合的交集,即分别计算集合1和集合2、集合1和集合3、以及集合2和集合3的交集。这三个交集包含了至少在两个数组中出现的所有唯一值。最后,通过合并这三个交集,得到一个包含所有符合条件的元素的集合,然后将该集合转换为列表并返回。

时间复杂度:

O(n + m + k)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在实现时选择使用集合而不是其他数据结构,例如列表或字典?
在实现中选择使用集合而不是列表或字典的主要原因是集合(set)在Python中是基于哈希表实现的,因此它能提供平均时间复杂度为O(1)的元素查找、插入和删除操作。这使得在进行交集和并集操作时非常高效。相比之下,如果使用列表,检查元素是否存在需要O(n)的时间复杂度,而字典虽然也具有快速查找的特点,但在本题中使用集合更为直接,因为我们只关心元素的存在性而不需要存储额外的键值对信息。集合还自动处理了元素的去重问题,这对于本题要求输出不重复的元素来说非常合适。
🦆
题解中提到的三个交集操作是并行执行的还是连续执行的?这种执行方式对性能有何影响?
题解中的三个交集操作(set1 & set2, set1 & set3, set2 & set3)是连续执行的。虽然在多线程或并行处理环境下,这些操作可以理论上并行执行以提高效率,但在标准的Python环境中,这些操作会按顺序执行。由于集合操作的时间复杂度相对较低,连续执行通常已经足够高效。并行执行可能会带来额外的复杂性和开销,例如线程的管理和同步,这在处理相对小的数据集时可能不是必要的。
🦆
合并三个交集后,是否可能出现重复元素需要再次去重,或者集合的特性已经自动处理了这一点?
合并三个交集后不会出现重复元素的问题,因为集合的特性已经自动处理了这一点。在Python中,集合是一个无序的、不包含重复元素的数据结构。当使用并集操作(|)合并多个集合时,任何重复的元素都只会被存储一次。因此,在题解中的合并操作(intersection12 | intersection13 | intersection23)中,所有重复的元素自动被去除,最终得到的结果集合中的元素都是唯一的。

相关问题