未分類

Intersection of Two Arrays

BinarySearch, Go, HashTable, LeetCode, Sort, TwoPointers

Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

###For Example:

1
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

  • Each element in the result must be unique.
  • The result can be in any order.
提示 解題應用
HashTable HashMap

Default:

1
2
3
func intersection(nums1 []int, nums2 []int) []int {
}

解答思路:

這次只是要找兩陣列有交集的部分，也就是說只要回傳兩陣列共同都有的值且不能重複，而最簡單的做法就是用hashmap來完成，只要其中一個陣列先存入hashmap，另一個只要核對就可以了，而先存入的那一個就算裡面有重覆也只是將key&value做覆蓋，並不會再新增一個，而這邊我們key就放陣列的值，value則是放boolean值在核對完後，用來確認是否已將此數放入結果之中，如果已經有放入了就不需要再放一次以避免重覆。

程式碼解說:

一開始先為結果初始化一空陣列及一個儲存的hashmap，而第一個迴圈就是遍歷第一個陣列並一一放入hashmap中，key值為元素值，而value則為false(此時尚未放入結果之中)，而就算陣列有值重覆，在hashamp之中也只是做覆蓋，而第二個迴圈開始遍歷第二個陣列核對其元素是否存在，如果存在表示該元素為兩陣列的交集之一，再來則是確認value(already)是否未放入結果之中，如果也尚未放入結果就可以安心將其值加入，並將該value值改成true，最後再第二個陣列核對完畢後回傳結果。

1
2
3
4
5
6
7
8
9
10
11
12
13
result := []int{}
hashMap := make(map[int]bool)
for _, v := range nums1 {
	hashMap[v] = false
}
for _, v := range nums2 {
	already, ok := hashMap[v]
	if ok && !already {
		hashMap[v] = true
		result = append(result, v)
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func intersection(nums1 []int, nums2 []int) []int {
	result := []int{}
	hashMap := make(map[int]bool)
	for _, v := range nums1 {
		hashMap[v] = false
	}
	for _, v := range nums2 {
		already, ok := hashMap[v]
		if ok && !already {
			hashMap[v] = true
			result = append(result, v)
		}
	}
	return result
}

總結:

要尋找兩陣列的交集且回傳時不可包含重覆的元素，此時先用hashmap來儲存第一個陣列，key值為該陣列的元素，而value則是boolean值，value為當另一陣列除了要確認元素是否存在，還必需要知道此元素是否己經放入結果之中以避免重覆。

分享到