给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
说明：
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays
---更新---
2021.11.06
python
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
"""
哈希法，时间优化
"""
if not nums1 or not nums2:
return []
from collections import defaultdict
m = defaultdict()
res = []
for i in nums1:
m[i] = 1
for i in nums2:
if i in m and m.get(i) > 0:
res.append(i)
m[i] = 0
return res
def intersection1(self, nums1: [int], nums2: [int]) -> [int]:
"""
暴力法 时间O(m*n)，空间O(max(m,n))
:param nums1:
:param nums2:
:return:
"""
if not nums1 or not nums2:
return []
res = list()
for i in range(len(nums1)):
for j in range(len(nums2)):
if nums1[i] == nums2[j] and nums2[j] not in res:
res.append(nums2[j])
return res
# 直接用自带数据结构方法，1.转set 2.取交集 3.转回list
def intersection2(self, nums1: [int], nums2: [int]) -> [int]:
return list(set(nums1) & set(nums2))
# 利用set属性-唯一性，遍历另一个数组，在set中则添加进结果中 时间O(n)
def intersection3(self, nums1: [int], nums2: [int]) -> [int]:
nums1 = set(nums1)
res_set = set()
for i in range(len(nums2)):
if nums2[i] in nums1:
res_set.add(nums2[i])
return list(res_set)
def intersection(self, nums1: [int], nums2: [int]) -> [int]:
"""
先排序，双指针，时间O(nlogn) 空间O(n)
:param nums1:
:param nums2:
:return:
"""
nums1.sort()
nums2.sort()
p1, p2 = 0, 0
len1, len2 = len(nums1), len(nums2)
res = list()
while p1 < len1 and p2 < len2:
num1, num2 = nums1[p1], nums2[p2]
if num1 == num2:
# 保证加入元素唯一
if not res or num1 != res[-1]:
res.append(num1)
p1 += 1
p2 += 1
elif num1 > num2:
p2 += 1
else:
p1 += 1
return res
if __name__ == "__main__":
nums1 = [1,3,4,3,5,7,8,8,8]
nums2 = [2,6,8,9,5,5]
test = Solution()
print(test.intersection1(nums1,nums2))
print(test.intersection2(nums1,nums2))
print(test.intersection3(nums1,nums2))
print(test.intersection(nums1,nums2))
golang
package main
import "fmt"
func main() {
var nums1 = []int{1, 5, 2, 3, 3, 7, 5, 4}
var nums2 = []int{10, 7, 4, 3}
res := intersection(nums1, nums2)
fmt.Println(res)
}
func intersection(nums1 []int, nums2 []int) []int {
m := make(map[int]int)
for _, v := range nums1 {
m[v] = 1
}
var res []int
// 利用count>0实现，相同值取一次
for _, v := range nums2 {
if count, ok := m[v]; ok && count > 0 {
res = append(res, v)
m[v]--
}
}
return res
}