题目描述
给定两个数组，编写一个函数来计算它们的交集。 示例 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
解题思路：
- 看到题目手首先想到求交集无法避免两个数组都要遍历一遍
- 先用最通用的思路解决一下，这里使用for嵌套循环, 循环中判断元素是否相等
- 调试后发现结果输出是[2,2,2,2]。忽略了重复元素的问题
- 使用一个hashmap存放相等的元素，这样只要在hashmap存在的元素扔进结果集即可
Code
func intersection(nums1 []int, nums2 []int) []int {
var res []int
//hashmap 用来去重
var temp = make(map[int]int)
for _, item1 := range nums1 {
for _, item2 := range nums2 {
//相等且不重复的元素扔进结果集
if item1 == item2 && temp[item1] != 1 {
temp[item1] = 1
res = append(res, item1)
}
}
}
return res
}
解题思路（进阶版）
- 通用版提交后，执行时间打败了10%。真的是是可忍孰不可忍，也感受到了来自内心的嘲讽
- Review了一遍刚刚的代码，发现自己蠢得可以。既然我已经使用了hashmap,完全可以将这个结构的作用升一下级
- 思路是这样，将nums1和nums2的嵌套循环拆出来变成顺序执行的循环，这样算法的复杂度便从m*n降低为m+n
- 在nums1循环时将其每一个元素在hashmap中标记为1，在nums2循环时，先做一个判断看该元素是否在1中出现过，如果出现过则标记为2，否则直接忽略
- 最后遍历hashmap，将标记为2的元素放入结果集
Code
func intersection(nums1 []int, nums2 []int) []int {
var res []int
//用于标记元素在nums1和nums2出现的状态
//1 表示在nums1中出现过
//2 表示在nums1和nums2中都出现过
var temp = make(map[int]int)
for _, item1 := range nums1 {
temp[item1] = 1;
}
for _, item2 := range nums2 {
if temp[item2] == 1 {
temp[item2] = 2;
}
}
for key, item3 := range temp {
if item3 == 2 {
res = append(res, key)
}
}
return res
}
总结
- 空间换时间是提高算法效率的常用思路
- 解题时尽量多思考，多思考一步也许会改变很多事情
- 晒一张最终版的提交结果
文档信息
- 本文作者：KcJia
- 本文链接：https://blog.kcjia.cn/2020/04/27/leetcode-349/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）