白羊的空间

Go 求两个数组切片交集

问题

两个数组切片求交集

情况1

1
2
s1 := []int{1, 4, 5, 4, 7, 8, 6, 2}
s2 := []int{2, 4, 6, 3, 4}

输出：

1
[2 4 6]

思路

采用map记录s1的元素，然后遍历s2，存在于map中并且不重复的增加到新切片中.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func intersect1(s1, s2 []int) ([]int, error) {
	if s1 == nil || s2 == nil {
		return nil, errors.New("nil silce")
	}
	result := []int{}
	if len(s1) == 0 || len(s2) == 0 {
		return result, nil
	}
	tempMap := make(map[int]bool)
	for _, v := range s1 {
		tempMap[v] = true
	}
	for _, v := range s2 {
		if c, ok := tempMap[v]; ok && c {
			result = append(result, v)
			tempMap[v] = false
		}
	}
	return result, nil
}

情况2

1
2
s1 := []int{1, 4, 5, 4, 7, 8, 6, 2}
s2 := []int{2, 4, 6, 3, 4}

输出：

1
[2 4 6 4]

思路

依然采用map记录s1的元素，不过需要记录元素出现的次数，然后遍历s2，存在于map中并且不重复的增加到新切片中.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func intersect2(s1, s2 []int) ([]int, error) {
	if s1 == nil || s2 == nil {
		return nil, errors.New("nil silce")
	}
	result := []int{}
	if len(s1) == 0 || len(s2) == 0 {
		return result, nil
	}
	tempMap := make(map[int]int)
	for _, v := range s1 {
		tempMap[v]++
	}
	for _, v := range s2 {
		if c, ok := tempMap[v]; ok && c > 0 {
			result = append(result, v)
			tempMap[v]--
		}
	}
	return result, nil
}

备注

两种情况均可以使用for循环嵌套来实现，不过对于出现次数的处理需要思考，并且时间复杂度也比是用map的方式要高。

Golang