leetcode
leetcode 301 ~ 350
两个数组的交集 II

两个数组的交集 II

难度:

标签:

题目描述

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

 

示例 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 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

代码结果

运行时间: 19 ms, 内存: 16.2 MB


/*
 * 思路:
 * 1. 使用Java Stream创建一个Map来存储nums1中每个元素的出现次数。
 * 2. 遍历nums2,过滤出在Map中存在且计数大于0的元素,
 *    并更新Map中的计数。
 * 3. 收集这些元素并返回数组。
 */
 
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
 
public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Long> map = Arrays.stream(nums1)
            .boxed()
            .collect(Collectors.groupingBy(e -> e, Collectors.counting()));
 
        List<Integer> result = Arrays.stream(nums2)
            .boxed()
            .filter(num -> map.getOrDefault(num, 0L) > 0)
            .peek(num -> map.put(num, map.get(num) - 1))
            .collect(Collectors.toList());
 
        return result.stream().mapToInt(i -> i).toArray();
    }
}

解释

方法:

该题解的思路是先对两个数组进行排序,然后使用双指针分别指向两个数组的起始位置。然后不断移动指针比较两个指针指向的元素大小,如果相等就把该元素加入答案,并同时移动两个指针;如果不相等,就移动指向较小数字的指针。这样遍历完一遍就能得到两个数组的交集。

时间复杂度:

O((n1+n2)log(n1+n2))

空间复杂度:

O(log(n1+n2))

代码细节讲解

🦆
在处理两个数组的交集时,为什么选择对数组进行排序而不是使用哈希表来存储元素频率?
选择对数组进行排序而不是使用哈希表的一个原因是排序后使用双指针方法可以在不需要额外空间的情况下找到交集,这对于内存使用较为友好。另外,排序和双指针方法在某些情况下可能比使用哈希表更有效,尤其是当数组已经部分或完全排序时。然而,使用哈希表在时间复杂度上通常更优(O(n)),但在空间复杂度上可能较高,尤其是当元素种类繁多时。
🦆
在双指针方法中,如果两个数组中的元素重复度较高,这种方法的效率如何?
如果两个数组中的元素重复度较高,双指针方法依然有效且效率不会受太大影响。在这种情况下,指针会较频繁地同时向前移动,因此可以快速找到所有的交集元素。排序的时间复杂度是O(n log n),而遍历和比较的时间复杂度是O(n),因此整体效率主要取决于排序步骤。
🦆
在进阶问题中提到如果`nums1`的大小比`nums2`小,是否考虑先对`nums1`进行排序,然后遍历`nums2`寻找交集?这样做的优势是什么?
如果`nums1`的大小比`nums2`小,考虑先对`nums1`进行排序然后遍历`nums2`是一个有效的策略。这样做的优势在于减少了排序的时间和空间成本,因为排序较小的数组比较快,且使用较小的数组建立哈希表(如果选择使用哈希表的策略)会占用更少的空间。此外,这种方式可以在遍历较大的数组时直接查找并确定交集元素,减少了不必要的计算和存储操作。
🦆
对于进阶问题中的场景,如果`nums2`的元素存储在磁盘上并且内存有限,如何优化算法以减少内存使用和IO操作?
如果`nums2`的元素存储在磁盘上并且内存有限,可以采用外部排序或者分块处理的方法来优化算法。首先,可以对`nums1`进行排序,并将其加载到内存中。然后,将`nums2`分成多个小块,每块单独从磁盘加载并排序,与内存中的`nums1`进行比较和交集查找。这种方法可以有效减少同时加载到内存中的数据量,从而减少内存使用。同时,通过减少对磁盘的全局扫描次数,也能降低IO操作。

相关问题

两个数组的交集

给定两个数组 nums1 和 nums2 ,返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

 

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的

 

提示:

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

查找共用字符

给你一个字符串数组 words ,请你找出所有在 words 的每个字符串中都出现的共用字符( 包括重复字符),并以数组形式返回。你可以按 任意顺序 返回答案。

 

示例 1:

输入:words = ["bella","label","roller"]
输出:["e","l","l"]

示例 2:

输入:words = ["cool","lock","cook"]
输出:["c","o"]

 

提示:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] 由小写英文字母组成