LeetCode_排序_简单_350.两个数组的交集II

1.题目

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

2.思路

（1）排序+双指针 与349.两个数组的交集这题的思路1类似，采用先排序然后双指针遍历的思想，不过本题不需要保证交集的互异性。除此之外，当不能一次加载所有的元素到内存中时，该方法就不能高效地对数组进行内排序，因而本方法不适合元素数量较大的情况！

（2）哈希表 ① 先创建长度为 Math.min(len1, len2) 的数组 res，它用来保存结果。此外还需创建一个哈希表 hashMap，并且将数组 nums1 中的元素以及对应出现的次数作为键值对； ② 遍历数组 nums1，将其中的元素以及对应出现的次数保存到 hashMap 中； ③ 遍历数组 nums2，如果 hashMap 中存在键 nums2[i] 对应的映射关系，并且键 nums2[i] 所对应的 value（即当前元素在数组 nums1 中出现的次数）不为0，则将 nums2[i] 添加到 res 中，且 nums2[i] 在 hashMap 中的次数减一； ④ 遍历结束后，将数组 res 中之前添加的结果部分返回即可。

3.代码实现（Java）

//思路1————排序+双指针
public int[] intersect(int[] nums1, int[] nums2) {
    int len1 = nums1.length;
    int len2 = nums2.length;
    int[] res = new int[Math.min(len1, len2)];
    //对数组nums1和nums2进行排序
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0, j = 0, k = 0;
    while (i