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

标签: 位运算 数组 哈希表

难度: Easy

给你三个整数数组 nums1、nums2 和 nums3 ，请你构造并返回一个 元素各不相同的 数组，且由 至少 在 两个 数组中出现的所有值组成。数组中的元素可以按 任意 顺序排列。

示例 1：

输入：nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
输出：[3,2]
解释：至少在两个数组中出现的所有值为：
- 3 ，在全部三个数组中都出现过。
- 2 ，在数组 nums1 和 nums2 中出现过。

示例 2：

输入：nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
输出：[2,3,1]
解释：至少在两个数组中出现的所有值为：
- 2 ，在数组 nums2 和 nums3 中出现过。
- 3 ，在数组 nums1 和 nums2 中出现过。
- 1 ，在数组 nums1 和 nums3 中出现过。

示例 3：

输入：nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
输出：[]
解释：不存在至少在两个数组中出现的值。

提示：

  • 1 <= nums1.length, nums2.length, nums3.length <= 100
  • 1 <= nums1[i], nums2[j], nums3[k] <= 100

Submission

运行时间: 26 ms

内存: 16.1 MB

from typing import List

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        set1, set2, set3 = set(nums1), set(nums2), set(nums3)
        
        # 计算任意两个集合的交集
        intersection12 = set1 & set2
        intersection13 = set1 & set3
        intersection23 = set2 & set3
        
        # 将交集结果合并到一个集合中
        result = intersection12 | intersection13 | intersection23
        
        return list(result)

Explain

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

时间复杂度: O(n + m + k)

空间复杂度: O(1)

from typing import List

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        # 将三个数组转换为集合，以去除重复元素
        set1, set2, set3 = set(nums1), set(nums2), set(nums3)
        
        # 计算任意两个集合的交集
        intersection12 = set1 & set2
        intersection13 = set1 & set3
        intersection23 = set2 & set3
        
        # 将交集结果合并到一个集合中
        result = intersection12 | intersection13 | intersection23
        
        # 将结果集合转换为列表并返回
        return list(result)

Explore

在实现中选择使用集合而不是列表或字典的主要原因是集合（set）在Python中是基于哈希表实现的，因此它能提供平均时间复杂度为O(1)的元素查找、插入和删除操作。这使得在进行交集和并集操作时非常高效。相比之下，如果使用列表，检查元素是否存在需要O(n)的时间复杂度，而字典虽然也具有快速查找的特点，但在本题中使用集合更为直接，因为我们只关心元素的存在性而不需要存储额外的键值对信息。集合还自动处理了元素的去重问题，这对于本题要求输出不重复的元素来说非常合适。

题解中的三个交集操作（set1 & set2, set1 & set3, set2 & set3）是连续执行的。虽然在多线程或并行处理环境下，这些操作可以理论上并行执行以提高效率，但在标准的Python环境中，这些操作会按顺序执行。由于集合操作的时间复杂度相对较低，连续执行通常已经足够高效。并行执行可能会带来额外的复杂性和开销，例如线程的管理和同步，这在处理相对小的数据集时可能不是必要的。

合并三个交集后不会出现重复元素的问题，因为集合的特性已经自动处理了这一点。在Python中，集合是一个无序的、不包含重复元素的数据结构。当使用并集操作（|）合并多个集合时，任何重复的元素都只会被存储一次。因此，在题解中的合并操作（intersection12 | intersection13 | intersection23）中，所有重复的元素自动被去除，最终得到的结果集合中的元素都是唯一的。