題目
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
解題思路
- 遍歷其中一個(gè)nums腐缤，將元素和其出現(xiàn)的次數(shù)放入map
- 再遍歷另一個(gè)nums，如果元素存在疚漆，則將元素append進(jìn)結(jié)果數(shù)組ret中，并將map中出現(xiàn)次數(shù)-1
Follow up:
- 如果數(shù)組是排好序的墓塌，可以一次遍歷兩個(gè)數(shù)組找到相交元素
- 一個(gè)數(shù)組小于另一個(gè)數(shù)組，可以將較小的數(shù)組放入map中
- 磁盤方案沒(méi)考慮
代碼
Intersect.go
package _350_Intersection_Two_Arrays_II
import "fmt"
func Intersect(nums1 []int, nums2 []int) []int {
len1 := len(nums1)
len2 := len(nums2)
var numsShort []int
var numsLong []int
if len1 < len2 {
numsShort = nums1
numsLong = nums2
} else {
numsShort = nums2
numsLong = nums1
}
fmt.Printf("short:%+v\n, long:%+v\n", numsShort, numsLong)
var numMap map[int]int
numMap = make(map[int]int)
for _, v := range numsShort {
numMap[v]++
}
fmt.Printf("map:%+v\n", numMap)
var ret []int
for _, v := range numsLong {
tmp, ok := numMap[v]
if ok && tmp > 0 {
numMap[v]--
ret = append(ret, v)
}
}
return ret
}
測(cè)試
Intersect_test.go
package _350_Intersection_Two_Arrays_II
import "testing"
func TestIntersect(t *testing.T) {
var tests = []struct{
input1 []int
input2 []int
} {
{[]int{1}, []int{1}, },
}
for _, v := range tests {
Intersect(v.input1, v.input2)
}
}
