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

解题思路

本题要求找到至少在三个数组中的两个数组中出现的元素。我们可以使用以下几种思路：

思路一：集合操作（推荐） 将三个数组转换为集合（去重），然后计算两两之间的交集。最后将所有交集合并，去除重复元素。这种方法简洁直观，易于理解。

思路二：哈希表统计 使用哈希表记录每个元素在哪些数组中出现过。遍历三个数组，对于每个元素，记录它出现在的数组编号。最后统计出现在至少两个数组中的元素。

思路三：位运算优化 对于每个元素，使用一个三位的二进制数来表示它在哪些数组中出现。第0位表示在nums1中出现，第1位表示在nums2中出现，第2位表示在nums3中出现。最后筛选出二进制表示中至少有两个1的元素。

三种方法的时间复杂度都是O(n)，其中n是所有数组元素的总数。考虑到代码的简洁性和可读性，推荐使用集合操作的方法。

代码实现

class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
        unordered_set<int> set3(nums3.begin(), nums3.end());
        
        unordered_set<int> result;
        
        // 计算三个两两交集
        for (int num : set1) {
            if (set2.count(num) || set3.count(num)) {
                result.insert(num);
            }
        }
        for (int num : set2) {
            if (set3.count(num)) {
                result.insert(num);
            }
        }
        
        return vector<int>(result.begin(), result.end());
    }
};

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)
        
        # 计算三个两两交集的并集
        result = (set1 & set2) | (set1 & set3) | (set2 & set3)
        
        return list(result)

public class Solution {
    public IList<int> TwoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        var set1 = new HashSet<int>(nums1);
        var set2 = new HashSet<int>(nums2);
        var set3 = new HashSet<int>(nums3);
        
        var result = new HashSet<int>();
        
        // 计算三个两两交集
        foreach (int num in set1) {
            if (set2.Contains(num) || set3.Contains(num)) {
                result.Add(num);
            }
        }
        foreach (int num in set2) {
            if (set3.Contains(num)) {
                result.Add(num);
            }
        }
        
        return result.ToList();
    }
}

var twoOutOfThree = function(nums1, nums2, nums3) {
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);
    const set3 = new Set(nums3);
    
    const result = new Set();
    
    // 计算三个两两交集
    for (const num of set1) {
        if (set2.has(num) || set3.has(num)) {
            result.add(num);
        }
    }
    for (const num of set2) {
        if (set3.has(num)) {
            result.add(num);
        }
    }
    
    return Array.from(result);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)其中 n = len(nums1) + len(nums2) + len(nums3)，需要遍历所有元素创建集合和计算交集
空间复杂度O(n)需要存储三个集合，最坏情况下每个集合包含对应数组的所有不重复元素