Preface

将两个切片按指定批次大小交替合并, 参数 batch 表示每次从切片取出元素个数。

常规实现(迭代)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// mergeSlicesByBatch 将两个切片按指定批次大小交替合并
// 参数 batch 表示每次从切片取出元素个数
func mergeSlicesByBatch[T any](s1, s2 []T, batch int) []T {
	merged := make([]T, 0, len(s1)+len(s2))
	// 提取指定批次的元素
	mergeTopN := func(slice []T, begin, batch int) int {
		end := begin + batch
		if end > len(slice) {
			end = len(slice)
		}
		if begin < end {
			merged = append(merged, slice[begin:end]...)
			begin = end
		}
		return begin
	}
	for i, j := 0, 0; i < len(s1) || j < len(s2); {
		i = mergeTopN(s1, i, batch)
		j = mergeTopN(s2, j, batch)
	}
	return merged
}

递归实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func crossMerge[T any](s1, s2 []T, batch int) []T {
	// s1长度<=N,直接合并
	if len(s1) <= batch {
		return slices.Concat(s1, s2)
	}
	// s2长度<=N,直接合并
	if len(s2) <= batch {
		return slices.Concat(s1[:batch], s2, s1[batch:])
	}
	// s1、s2都大于N,递归处理
	right := crossMerge[T](s1[batch:], s2[batch:], batch)
	return slices.Concat(s1[:batch], s2[:batch], right)
}

这里使用slices.Concat() 函数来合并切片, 而不是append(),因为append会修改原始slice。

方案对比

方案 时间复杂度 空间复杂度 适用场景
迭代 O(M+N) O(M+N) 大多数场景,尤其是内存受限的情况
递归 O(M+N) O(M+N) 额外O(M+N) 简洁优雅,不易出错(缺点:递归合并需分配临时空间)

单元测试

1
2
3
4
5
6
7
func Test_mergeSlicesByBatch(t *testing.T) {
	slice1 := []int{1, 2, 3, 4, 5, 6, 7, 8}
	slice2 := []int{'A', 'B', 'C', 'D', 'E', 'F', 'G'}
	merged := crossMerge(slice1, slice2, 3)
	expected := []int{1, 2, 3, 'A', 'B', 'C', 4, 5, 6, 'D', 'E', 'F', 7, 8, 'G'}
	assert.EqualValues(t, expected, merged)
}