两个有序集合的合并

calendar Sep 21, 2024 · 2 min read · algorithm 中文  ·
Share on: linkedin copy

Overview

双指针法的解决思路：

  1. 初始化两个指针：分别指向两个有序集合的起始位置。
  2. 比较当前指针指向的元素：
    • 如果集合1的元素小于集合2的元素，将集合1的元素放入结果集中，并将集合1的指针向后移动。
    • 如果集合2的元素小于集合1的元素，将集合2的元素放入结果集中，并将集合2的指针向后移动。
    • 如果两个集合的元素相等，则可以选择将其中一个元素加入结果集，然后两个指针都向后移动。
  3. 处理剩余元素：当其中一个集合的所有元素都已合并到结果集中，另一集合可能还有剩余元素。此时直接将剩余元素加入结果集中。
  4. 返回结果集：所有元素被合并后返回结果。

代码：

 1package main 
 2
 3import "fmt"
 4
 5func mergeSet(set1, set2 []int) []int {
 6    result := []int{}
 7    
 8    i, j := 0, 0
 9
10    for i < len(set1) && j < len(set2) {
11        // 1. 比较大小，小的先走
12        if set1[i] < set2[j] {
13            result = append(result, set1[i])
14            i++
15        } else if set1[i] > set2[j] {
16            // 2. 大的后走
17            result = append(result, set2[j])
18            j++
19        } else {
20            // 3. 相等时候插入一个，指针都走一步
21            result = append(result, set1[i])
22            result = append(result, set2[j])
23            i++
24            j++
25        }
26    }
27
28    // 如果有剩下的
29    for i < len(set1) {
30        result = append(result, set1[i])
31        i++
32    }
33
34    for j < len(set2) {
35        result = append(result, set2[j])
36        j++
37    }
38
39
40    return result
41}
42
43
44func main() {
45    // 集合1
46    a := []int{1,2,3,4,5}
47    
48    // 集合2
49    b := []int{3,4,5,6,7}
50
51    result := mergeSet(a, b)
52
53    fmt.Println(result)
54    
55}

时间复杂度：

  • 双指针法的时间复杂度为O(n+m)，其中n和m分别为两个集合的长度。因为每个集合的每个元素只会被遍历一次，所以整体时间复杂度是线性级别的。

合并逻辑调整：一轮for循环实现方式

我们可以将双指针逻辑合并为一个更简洁的单个for循环，进一步简化代码。通过调整循环条件，可以避免使用两个单独的for循环处理剩余元素的逻辑。

优化后的代码：

 1package main 
 2
 3import "fmt"
 4
 5func mergeSetOneLoop(set1, set2 []int) []int {
 6    result := []int{}
 7    
 8    i, j := 0, 0
 9
10    // 一个循环内处理合并
11    for i < len(set1) || j < len(set2) {
12        if i < len(set1) && (j >= len(set2) || set1[i] < set2[j]) {
13            result = append(result, set1[i])
14            i++
15        } else if j < len(set2) && (i >= len(set1) || set1[i] > set2[j]) {
16            result = append(result, set2[j])
17            j++
18        } else {
19            result = append(result, set1[i])
20            i++
21            j++
22        }
23    }
24
25    return result
26}
27
28func main() {
29    // 集合1
30    a := []int{1,2,3,4,5}
31    
32    // 集合2
33    b := []int{3,4,5,6,7}
34
35    result := mergeSetOneLoop(a, b)
36
37    fmt.Println(result) // [1 2 3 3 4 4 5 5 6 7]
38}

代码解释：

  1. 使用一个for循环控制流程，条件为i < len(set1) || j < len(set2)，即当任意一个集合没有遍历完时，继续合并。
  2. 在循环中判断：
    • 当i没有超出set1的长度且j已经超出set2的长度，或者set1[i]小于set2[j]时，将set1[i]添加到结果中，并移动i。
    • 同理，处理set2中的元素。
    • 当set1[i]和set2[j]相等时，将set1[i]或set2[j]（二者相等）添加到结果集中，并同时移动两个指针。

时间复杂度：

  • 单循环法的时间复杂度依然是O(n+m)，因为每个元素只被处理一次，整体算法的时间复杂度是线性的。

两种实现方式的对比

解决方法 时间复杂度 优点 缺点
双指针法（两个for循环） O(n + m) 逻辑清晰、代码结构分明，容易理解 使用多个for循环，代码稍微冗长
单循环法 O(n + m) 代码简洁，合并剩余元素时不需要额外的循环 条件判断稍显复杂，理解门槛较高