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

🟢   🔖  位运算 数组 哈希表  🔗 力扣 LeetCode

题目

Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out of the three arrays. You may return the values in any order.

Example 1:

Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]

Output: [3,2]

Explanation: The values that are present in at least two arrays are:

• 3, in all three arrays.
• 2, in nums1 and nums2.

Example 2:

Input: nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]

Output: [2,3,1]

Explanation: The values that are present in at least two arrays are:

• 2, in nums2 and nums3.
• 3, in nums1 and nums2.
• 1, in nums1 and nums3.

Example 3:

Input: nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]

Output: []

Explanation: No value is present in at least two arrays.

Constraints:

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

题目大意

给你三个整数数组 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

解题思路

1. 利用集合去重：将每个数组中的元素转换为集合 set1、set2 和 set3，消除重复值。
2. 统计出现频次：创建一个 Map，用于记录每个元素出现在不同集合中的次数。
3. 遍历集合：将三个集合的元素依次加入 Map，并更新每个元素的频次。
4. 筛选结果：从 Map 中提取出现次数大于或等于 2 的元素，构造返回结果。

复杂度分析

• 时间复杂度：O(n1 + n2 + n3 + u)

  • 构建集合的时间为 O(n1 + n2 + n3)，其中 n1, n2, n3 是三个数组的长度。
  • 遍历集合统计频次的时间为 O(u1 + u2 + u3)，其中 u1, u2, u3 是三个集合的大小。
  • 最后筛选结果的时间为 O(u)，其中 u 是所有元素的总数量。
  • 总复杂度为 O(n1 + n2 + n3 + u)。

• 空间复杂度：O(u)，其中 u 是所有不同元素的总数量，使用了三个集合和一个 Map。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @return {number[]}
 */
var twoOutOfThree = function (nums1, nums2, nums3) {
	let set1 = new Set(nums1);
	let set2 = new Set(nums2);
	let set3 = new Set(nums3);
	let freq = new Map();

	// 统计频次
	const count = (set) => {
		for (let num of set) {
			freq.set(num, (freq.get(num) || 0) + 1);
		}
	};

	count(set1);
	count(set2);
	count(set3);

	// 筛选出现次数 >= 2 的元素
	return [...freq.keys()].filter((i) => freq.get(i) >= 2);
};