题目描述

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

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

示例 2:

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

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

进阶：

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

思路

哈希表

由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
这里有个动态图解释

  1. public int[] intersect(int[] nums1, int[] nums2) {
  2.     // 保证第一个链表是短的
  3.     if (nums1.length > nums2.length) {
  4.         return intersect(nums2, nums1);
  5.     }
  6.     // 将元素加入到 map 中
  7.     Map<Integer, Integer> map = new HashMap<>();
  8.     for (int num : nums1) {
  9.         // 获取值，如果获取不到返回默认值
  10.         int count = map.getOrDefault(num, 0) + 1;
  11.         map.put(num, count);
  12.     }
  13.     // 数组最终的位置
  14.     // 由于 num1 在这个步骤之后不会再使用，而且 num1 较长，因此将这个数组用来存结果，废物利用
  15.     int index = 0;
  16.     for (int num : nums2) {
  17.         // 获取值，如果获取不到返回默认值
  18.         int count = map.getOrDefault(num, 0);
  19.         if (count > 0) {
  20.             nums1[index++] = num;
  21.             map.put(num, --count);
  22.         }
  23.     }
  24.     return Arrays.copyOfRange(nums1, 0, index);
  25. }

image.png

排序 + 双指针

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

  2. public int[] intersect(int[] nums1, int[] nums2) {
  3.     Arrays.sort(nums1);
  4.     Arrays.sort(nums2);
  5.     int length1 = nums1.length, length2 = nums2.length;
  6.     int[] intersection = new int[Math.min(length1, length2)];
  7.     int index1 = 0, index2 = 0, index = 0;
  8.     while (index1 < length1 && index2 < length2) {
  9.         if (nums1[index1] < nums2[index2]) {
  10.             index1++;
  11.         } else if (nums1[index1] > nums2[index2]) {
  12.             index2++;
  13.         } else {
  14.             intersection[index] = nums1[index1];
  15.             index1++;
  16.             index2++;
  17.             index++;
  18.         }
  19.     }
  20.     return Arrays.copyOfRange(intersection, 0, index);
  21. }

image.png

进阶

image.png

。。。。能想到哈希表，结构也想出来了，但是没有想到能用减法操作