350. 两个数组的交集 II

🟢   🔖  数组 哈希表 双指针 二分查找 排序  🔗 力扣 LeetCode

题目

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

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

Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [4,9]

Explanation: [9,4] is also accepted.

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

题目大意

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入： nums1 = [1,2,2,1], nums2 = [2,2]

输出：[2,2]

示例 2:

输入： nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出：[4,9]

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

进阶：

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小，哪种方法更优？
• 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解题思路

1. 排序：

   • 先对 nums1 和 nums2 两个数组进行排序，使得两个数组的元素按从小到大的顺序排列。排序后的数组更容易进行交集的查找，因为我们可以通过一次遍历来寻找相同的元素。

2. 双指针法：

   • 使用两个指针 i 和 j 分别指向 nums1 和 nums2 的当前元素。
   • 通过比较 nums1[i] 和 nums2[j] 的值：
     • 如果 nums1[i] < nums2[j]，则 nums1[i] 小于 nums2[j]，所以我们将 i 向右移动，继续检查下一个 nums1 的元素。
     • 如果 nums1[i] > nums2[j]，则 nums2[j] 小于 nums1[i]，因此我们将 j 向右移动，继续检查下一个 nums2 的元素。
     • 如果 nums1[i] == nums2[j]，则说明找到了一个交集元素，加入结果数组 res，并将两个指针都向右移动，继续比较下一对元素。

3. 返回结果：

   • 当任一指针遍历完其数组后，停止比较，返回交集结果 res。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
	// 对两个数组进行排序
	nums1.sort((a, b) => a - b);
	nums2.sort((a, b) => a - b);

	let res = [];
	let i = 0,
		j = 0;

	// 使用双指针法查找交集
	while (i < nums1.length && j < nums2.length) {
		if (nums1[i] < nums2[j]) {
			i++; // nums1 元素较小，向右移动指针
		} else if (nums1[i] > nums2[j]) {
			j++; // nums2 元素较小，向右移动指针
		} else {
			res.push(nums1[i]); // 发现相等的元素，加入结果
			i++;
			j++;
		}
	}

	return res;
};

复杂度分析

• 时间复杂度：O(n log n + m log m)

  • 排序操作的时间复杂度是 O(n log n) 和 O(m log m)，其中 n 和 m 分别是两个数组的长度。
  • 双指针遍历的时间复杂度是 O(n + m)，因为最多需要遍历两个数组中的每个元素一次。
  • 因此，总的时间复杂度是 O(n log n + m log m)。

• 空间复杂度：O(min(n, m))，使用了额外的 res 数组来存储交集元素，交集数组的长度最多为 min(n, m)。

进阶问题

1. 如果给定的数组已经排好序，如何优化你的算法？

• 如果给定的数组已经排好序，可以直接使用 双指针法（不需要先排序）。这将大大减少时间复杂度，因为排序操作的时间复杂度是 O(n log n)，而双指针遍历两个已排序数组的时间复杂度是 O(n + m)，即使数组没有排序，排序也是不必要的。
• 这样，时间复杂度从 O(n log n + m log m) 优化为 O(n + m)，其中 n 和 m 是两个数组的长度。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
	let res = [];
	let i = 0,
		j = 0;

	// 双指针法遍历已排序的数组
	while (i < nums1.length && j < nums2.length) {
		if (nums1[i] < nums2[j]) {
			i++; // nums1 元素较小，向右移动指针
		} else if (nums1[i] > nums2[j]) {
			j++; // nums2 元素较小，向右移动指针
		} else {
			res.push(nums1[i]); // 发现相等的元素，加入结果
			i++;
			j++;
		}
	}

	return res;
};

复杂度分析

• 时间复杂度： O(n + m)，无需排序。
• 空间复杂度： O(min(n, m))，存储交集。

---

2. 如果 nums1 的大小比 nums2 小，哪种方法更优？

• 如果 nums1 的大小比 nums2 小，可以使用哈希集合来存储较小数组的元素，然后遍历较大的数组，检查每个元素是否在哈希集合中出现。
• 这样可以减少不必要的比较，避免多次遍历较大的数组。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
	// 保证 nums1 是较小的数组
	if (nums1.length > nums2.length) {
		[nums1, nums2] = [nums2, nums1];
	}

	let res = [];
	let set = new Set(nums1);

	for (let num of nums2) {
		if (set.has(num)) {
			res.push(num);
			set.delete(num); // 防止重复的元素
		}
	}

	return res;
};

复杂度分析

• 时间复杂度： O(n + m)，其中 n 是较小数组的长度，m 是较大数组的长度。
• 空间复杂度： O(n)，需要存储较小数组的元素。

---

3. 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

• 由于 nums2 太大，不能一次加载到内存中，我们可以将 nums2 存储在磁盘上，分批读取其元素。
• 外部排序：可以使用外部排序技术，将 nums2 分为多个块，每个块可以加载到内存中。我们对每个块进行排序，然后逐块与 nums1 比较，寻找交集。
• 迭代读取：将 nums2 分成多个小块，每次只读取一个块，然后逐步与 nums1 中的元素进行比较。
• 哈希方法：我们可以使用哈希表存储 nums1 的元素，nums2 每读取一个元素就与哈希表进行比较。如果该元素存在于哈希表中，就认为它是交集元素。

具体步骤：

1. 将 nums1 加载到内存中并构建哈希表。
2. 将 nums2 从磁盘按块读取，每次读取一小部分。
3. 对于每次读取的 nums2 块，逐个元素与 nums1 中的哈希表进行比对，找到交集。
4. 将交集元素存储或输出。

代码（伪代码示例）

// 假设读取文件时一次只读取一个元素
var intersect = function (nums1, filePathToNums2) {
	let set = new Set(nums1);
	let res = [];

	// 假设 readChunk 是一个函数，能从磁盘中分批读取 nums2 的元素
	while (true) {
		let chunk = readChunk(filePathToNums2);
		if (!chunk || chunk.length === 0) break;

		for (let num of chunk) {
			if (set.has(num)) {
				res.push(num);
				set.delete(num); // 确保没有重复的交集元素
			}
		}
	}

	return res;
};

复杂度分析

• 时间复杂度： O(n + m)，其中 n 是 nums1 的大小，m 是 nums2 读取的总量。
• 空间复杂度： O(n)，需要存储 nums1 的哈希表。

相关题目

题号	标题	题解	标签	难度	力扣
349	两个数组的交集	[✓]	数组 哈希表 双指针 2+	🟢	🀄️ 🔗
1002	查找共用字符	[✓]	数组 哈希表 字符串	🟢	🀄️ 🔗
2143	在两个数组的区间中选取数字 🔒		数组 动态规划	🔴	🀄️ 🔗
2215	找出两数组的不同	[✓]	数组 哈希表	🟢	🀄️ 🔗
2248	多个数组求交集		数组 哈希表 计数 1+	🟢	🀄️ 🔗
2540	最小公共值		数组 哈希表 双指针 1+	🟢	🀄️ 🔗