题目描述:
给定两个数组,编写一个函数来计算它们的交集。
示例 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 元素个数大于 nums2,则交换数组元素。
对于 nums1 的每个元素,添加到 HashMap m 中,如果元素已经存在则增加对应的计数。
初始化 k = 0,记录当前交集元素个数。
遍历数组 nums2:
检查元素在 m 是否存在,若存在且计数为正:
将元素拷贝到 nums1[k],且 k++。
减少 m 中对应元素的计数。
返回 nums1 前 k 个元素。
2.排序
适用场景:输入的数据有序
对数组 nums1 和 nums2 排序。
初始化指针 i,j 和 k 为 0。
指针 i 指向 nums1,指针 j 指向 nums2:
如果 nums1[i] < nums2[j],则 i++。
如果 nums1[i] > nums2[j],则 j++。
如果 nums1[i] == nums2[j],将元素拷贝到 nums1[k],且 i++,j++,k++。
返回数组 nums1 前 k 个元素。