【哈希表】leetcode349_两个数组的交集

标签：end   etc   实现   因此   make   unsafe   pre   一个   intersect   

编号349：两个数组的交集

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

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

说明：

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

思路

可以发现，貌似用数组做哈希表可以解决这道题目，把nums1的元素，映射到哈希数组的下表上，然后在遍历nums2的时候，判断是否出现过就可以了。但是题目并没有说明限制数组数值大小，如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。不像前面的两道题，数组存储英文的26个字母，是固定且个数较少，比较适合采用数组。

因此这题我们采用set集合，注意，在golang中是没有set类型的，我们可以采用map类型代替，用map的key作为唯一值并进行去重。例如输入：nums1 = [1,2,2,1]， nums2 = [2,2]，利用map[int]bool存储nums1就变成了mp={1:true,2:true}，可以节省一部分空间。此时再遍历num2中的元素，如果有交集的元素则存入result结果集就好。

具体代码如下：

func intersection(nums1 []int, nums2 []int) []int {
	mp := make(map[int]bool)
	result := make([]int, 0)  //存放交集元素

	for _, n1 := range nums1 { //将nums1中的数作为mp中的键，实现去重效果
		mp[n1] = true
	}

	for _, n2 := range nums2 {
		if mp[n2] {
			mp[n2] = false
			result = append(result, n2)
		}
	}

	return result
}

这里可以做个空间优化：map的value值是布尔型，这会导致set多占用内存空间，解决这个问题，则可以将其替换为空结构。在Go中，空结构通常不使用任何内存。即unsafe.Sizeof(struct{}{}) 的结果为 0。

func intersection(nums1 []int, nums2 []int) []int {
	mp := make(map[int]struct{})
	result := make([]int, 0)

	for _, n1 := range nums1 { //将nums1中的数作为mp中的键，实现去重效果
		mp[n1] = struct{}{}
	}

	for _, n2 := range nums2 {
		if _, ok := mp[n2]; ok {
			result = append(result, n2)
			delete(mp, n2)
		}
	}

	return result
}

【哈希表】leetcode349_两个数组的交集

标签：end   etc   实现   因此   make   unsafe   pre   一个   intersect   

原文地址：https://www.cnblogs.com/zmk-c/p/14401011.html