2248. 多个数组求交集

🟢   🔖  数组 哈希表 计数 排序  🔗 力扣 LeetCode

题目

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums sorted in ascending order.

Example 1:

Input: nums = [[3 ,1,2,4 ,5],[1,2,3 ,4],[3 ,4 ,5,6]]

Output: [3,4]

Explanation:

The only integers present in each of nums[0] = [3 ,1,2,4 ,5], nums[1] = [1,2,3 ,4], and nums[2] = [3 ,4 ,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]

Output: []

Explanation:

There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints:

• 1 <= nums.length <= 1000
• 1 <= sum(nums[i].length) <= 1000
• 1 <= nums[i][j] <= 1000
• All the values of nums[i] are unique.

题目大意

给你一个二维整数数组 nums ，其中 nums[i] 是由 不同 正整数组成的一个非空数组，按 升序排列 返回一个数组，数组中的每个元素在 nums 所有数组 中都出现过。

示例 1：

输入： nums = [[3 ,1,2,4 ,5],[1,2,3 ,4],[3 ,4 ,5,6]]

输出：[3,4]

解释：

nums[0] = [3 ,1,2,4 ,5]，nums[1] = [1,2,3 ,4]，nums[2] = [3 ,4 ,5,6]，在 nums 中每个数组中都出现的数字是 3 和 4 ，所以返回 [3,4] 。

示例 2：

输入： nums = [[1,2,3],[4,5,6]]

输出：[]

解释：

不存在同时出现在 nums[0] 和 nums[1] 的整数，所以返回一个空列表 [] 。

提示：

• 1 <= nums.length <= 1000
• 1 <= sum(nums[i].length) <= 1000
• 1 <= nums[i][j] <= 1000
• nums[i] 中的所有值 互不相同

解题思路

1. 交集的定义：

   • 交集中的每个元素必须出现在所有数组中。
   • 如果一个数字出现的次数等于数组的数量 nums.length，那么它属于交集。

2. 利用频率统计：

   • 用一个哈希表（对象）统计每个数字出现的次数。
   • 遍历所有数组，将每个数字出现的次数存入哈希表。

3. 过滤结果：

   • 筛选出出现次数等于 nums.length 的数字，即为交集。
   • 由于取对象的 keys 会自动从小到大排序，因此输出的顺序符合要求。

复杂度分析

• 时间复杂度：O(n * m + k log k)
  • 遍历所有数组统计频率：O(n * m)，其中 n 是数组数量，m 是单个数组的平均长度。
  • 过滤和排序：O(k log k)，其中 k 是哈希表中符合条件的数字数量。
  • 总复杂度：O(n * m + k log k)。
• 空间复杂度：O(u)，其中 u 是所有数组中不重复数字的数量，使用了一个哈希表存储数字频率。

代码

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var intersection = function (nums) {
	let freq = {};

	// 统计每个数字的出现次数
	for (let arr of nums) {
		for (let num of arr) {
			freq[num] = (freq[num] || 0) + 1;
		}
	}

	// 筛选出出现次数等于数组数的数字，并排序
	return Object.keys(freq)
		.filter((i) => freq[i] == nums.length)
		.map(Number)
		.sort((a, b) => a - b);
};

相关题目

题号	标题	题解	标签	难度	力扣
349	两个数组的交集	[✓]	数组 哈希表 双指针 2+	🟢	🀄️ 🔗
350	两个数组的交集 II	[✓]	数组 哈希表 双指针 2+	🟢	🀄️ 🔗
1198	找出所有行中最小公共元素 🔒		数组 哈希表 二分查找 2+	🟠	🀄️ 🔗
1213	三个有序数组的交集 🔒		数组 哈希表 二分查找 1+	🟢	🀄️ 🔗
2215	找出两数组的不同	[✓]	数组 哈希表	🟢	🀄️ 🔗