给定两个数组，编写一个函数来计算它们的交集
示例1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]
示例2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]
说明：
==》map映射
=================================Python===============================
class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: dic1 = {} dic2 = {} for val in nums1: if val in dic1: dic1[val] += 1 else: dic1[val] = 1 for val2 in nums2: if val2 in dic2: dic2[val2] += 1 else: dic2[val2] = 1 res = [] for key, value in dic1.items(): if key in dic2: for _ in range(min(dic2[key], value)): res.append(key) return res
----------------------------优化------------------------------
========================================Go======================================
func intersect(nums1 []int, nums2 []int) []int { m0 := map[int]int{} for _, v := range nums1 { m0[v] += 1 } k := 0 for _, v := range nums2 { if m0[v] > 0 { m0[v] -= 1 nums2[k] = v k++ } } return nums2[0:k] }
=====================================Java=================================
class Solution { public int[] intersect(int[] nums1, int[] nums2) { HashMap<Integer, Integer> map1 = new HashMap<>(); for (int num: nums1){ int count = map1.getOrDefault(num, 0) + 1; map1.put(num, count); } int[] res = new int[nums1.length]; int index = 0; for (int num: nums2){ int count = map1.getOrDefault(num, 0); if (count > 0) { count--; res[index++] = num; if (count > 0) { map1.put(num, count); } else { map1.remove(num); } } } return Arrays.copyOfRange(res, 0, index); } }
进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
对应进阶问题三，如果内存十分小，不足以将数组全部载入内存，那么必然也不能使用哈希这类费空间的算法，只能选用空间复杂度最小的算法。
一般说排序算法都是针对于内部排序，一旦涉及到跟磁盘打交道（外部排序），则需要特殊的考虑。归并排序是天然适合外部排序的算法，可以将分割后的子数组写到单个文件中，归并时将小文件合并为更大的文件。当两个数组均排序完成生成两个大文件后，即可使用双指针遍历两个文件，如此可以使空间复杂度最低。
双指针
===============Python=============
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
i = j = 0
res = []
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
res.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return res
============Go==========
func intersect(nums1 []int, nums2 []int) []int {
i, j, k := 0, 0, 0
sort.Ints(nums1)
sort.Ints(nums2)
for i < len(nums1) && j < len(nums2) {
if nums1[i] > nums2[j] {
j++
} else if nums1[i] < nums2[j] {
i++
} else {
nums1[k] = nums1[i]
i++
j++
k++
}
}
return nums1[:k]
}
======================Java====================
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int l1 = nums1.length;
int l2 = nums2.length;
int i = 0;
int j = 0;
int index = 0;
while (i < l1 && j < l2) {
if (nums1[i] == nums2[j]) {
nums1[index++] = nums1[i];
i ++;
j ++;
} else if (nums1[i] > nums2[j]) {
j ++;
} else {
i ++;
}
}
return Arrays.copyOfRange(nums1, 0, index);
}
}
原文：https://www.cnblogs.com/liushoudong/p/13492594.html