用KMP鸿蒙合并两个有序数组 - 算法实现

本文介绍了一种基于双指针的归并算法，用于合并两个已排序数组。算法通过初始化两个指针分别指向数组开头，比较元素大小后逐步移动指针，最终生成有序合并结果。代码实现包含输入解析、排序检查、合并逻辑和过程展示四个模块，支持多种输入格式并自动处理异常情况。核心算法时间复杂度为O(m+n)，具有高效稳定的特点，适用于归并排序、数据库查询等场景。文章详细解析了Kotlin实现代码，展示了防御性编程和函数式编程的

2501_94534814

608人浏览 · 2025-12-06 16:03:05

2501_94534814 · 2025-12-06 16:03:05 发布

在这里插入图片描述

摘要

合并两个有序数组工具实现了将两个已排序的数组合并成一个新的有序数组的功能。本文详细解析了基于双指针的归并算法实现，包括输入解析、排序检查、合并逻辑、过程展示等核心功能的代码细节。

1. 算法背景

1.1 问题描述

给定两个已排序的数组，将它们合并成一个新的有序数组，保持原有顺序。

示例：

数组1：[1, 3, 5, 7]
数组2：[2, 4, 6, 8]
合并结果：[1, 2, 3, 4, 5, 6, 7, 8]

1.2 应用场景

归并排序的核心子过程
合并两个有序链表
多路归并算法
数据库合并查询结果
日志文件合并

2. 核心算法原理

使用双指针技术：

初始化两个指针，分别指向两个数组的开头
比较两个指针指向的元素，将较小的元素加入结果数组
移动指向较小元素的指针
重复步骤 2-3，直到其中一个数组遍历完毕
将剩余数组的所有元素加入结果数组

3. 代码实现详细解析

3.1 输入解析模块

var arr1Str: String? = null
var arr2Str: String? = null

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("arr1=", ignoreCase = true) -> {
                arr1Str = line.substringAfter("=").trim()
            }
            line.startsWith("arr2=", ignoreCase = true) -> {
                arr2Str = line.substringAfter("=").trim()
            }
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持从输入字符串中提取两个数组。首先声明两个可空字符串变量 arr1Str 和 arr2Str，分别用于存储第一个和第二个数组的字符串表示。使用可空类型是因为这些参数可能不存在或解析失败，需要后续验证。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行，得到一个干净的字符串列表。这种链式调用是 Kotlin 中常见的处理集合的方式，代码简洁且易于理解。

接下来使用 forEach 遍历每一行，使用 when 表达式进行模式匹配。when 表达式是 Kotlin 中强大的条件判断结构，比传统的 if-else 链更简洁清晰。

第一个分支处理 arr1= 格式的输入。使用 startsWith("arr1=", ignoreCase = true) 检查行是否以 “arr1=” 开头（忽略大小写），如果匹配，使用 substringAfter("=") 提取等号后面的部分作为第一个数组的字符串，trim() 去除空白字符。这种格式支持用户明确指定第一个数组。

第二个分支处理 arr2= 格式的输入，使用相同的方式提取第二个数组的字符串。两个分支的处理逻辑完全对称，使代码结构清晰统一。

3.2 数组解析和排序检查

val arr1 = arr1Str!!.split(",", ";", " ")
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .mapNotNull { it.toDoubleOrNull() }
    .sorted()

val arr2 = arr2Str!!.split(",", ";", " ")
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .mapNotNull { it.toDoubleOrNull() }
    .sorted()

fun isSorted(arr: List<Double>): Boolean {
    for (i in 0 until arr.size - 1) {
        if (arr[i] > arr[i + 1]) return false
    }
    return true
}

代码解析：

这段代码将数组字符串解析为数字列表，并检查是否已排序。首先使用 split(",", ";", " ") 按逗号、分号或空格分割字符串。支持多种分隔符提高了灵活性，用户可以输入 1,3,5,7、1;3;5;7 或 1 3 5 7 等格式。

然后使用 map { it.trim() } 去除每个分割后元素的空白字符，确保即使输入中有多余的空格也能正确解析。例如，输入 "1, 3, 5, 7" 会被正确处理。

接下来使用 filter { it.isNotEmpty() } 过滤空字符串。如果在分割后产生空字符串（例如输入 "1,,3"），这些空字符串会被过滤掉，避免解析错误。

然后使用 mapNotNull { it.toDoubleOrNull() } 将每个字符串转换为数字。toDoubleOrNull() 安全地将字符串转换为双精度浮点数，如果转换失败返回 null。mapNotNull 会自动过滤掉 null 值，只保留成功转换的数字。这样即使输入中包含非数字字符，也能部分解析出有效的数字。

最后使用 sorted() 对数组进行排序。这是一个重要的处理：即使输入数组可能已经排序，这里也重新排序一次，确保数组确实是有序的。这是防御性编程的体现，提高了代码的健壮性。

isSorted 函数用于检查数组是否已经排序。函数遍历数组，比较相邻元素，如果发现前一个元素大于后一个元素，说明数组未排序，返回 false。如果所有相邻元素都满足非递减关系，返回 true。这个函数用于在输出中提示用户数组是否已排序，虽然代码中已经自动排序了，但这个检查提供了有用的信息。

3.3 合并算法核心函数

fun mergeArrays(a1: List<Double>, a2: List<Double>): List<Double> {
    val result = mutableListOf<Double>()
    var i = 0
    var j = 0

    while (i < a1.size && j < a2.size) {
        if (a1[i] <= a2[j]) {
            result.add(a1[i])
            i++
        } else {
            result.add(a2[j])
            j++
        }
    }

    while (i < a1.size) {
        result.add(a1[i])
        i++
    }

    while (j < a2.size) {
        result.add(a2[j])
        j++
    }

    return result
}

代码解析：

这是合并算法的核心实现，使用经典的双指针归并算法。函数首先创建一个可变列表 result 用于存储合并结果，mutableListOf 创建了一个可以动态添加元素的列表。然后初始化两个指针 i 和 j，分别指向两个数组的开头，初始值都为 0。

第一个 while 循环是核心的合并逻辑，条件是 i < a1.size && j < a2.size，即两个指针都还在各自数组的范围内。在循环内部，比较两个指针指向的元素 a1[i] 和 a2[j]。

如果 a1[i] <= a2[j]，说明第一个数组的当前元素较小或相等，将其添加到结果数组中，然后移动第一个数组的指针 i++。注意这里使用 <= 而不是 <，这保证了算法的稳定性：当两个元素相等时，优先选择第一个数组的元素，保持原有的相对顺序。

如果 a2[j] < a1[i]，说明第二个数组的当前元素较小，将其添加到结果数组中，然后移动第二个数组的指针 j++。

这个循环会一直执行，直到其中一个数组的所有元素都被处理完毕（即 i >= a1.size 或 j >= a2.size）。此时，另一个数组可能还有剩余元素，需要将这些剩余元素也添加到结果数组中。

接下来的两个 while 循环处理剩余元素。第一个循环处理第一个数组的剩余元素：如果 i < a1.size，说明第一个数组还有未处理的元素，将它们全部添加到结果数组中。第二个循环处理第二个数组的剩余元素：如果 j < a2.size，说明第二个数组还有未处理的元素，将它们全部添加到结果数组中。

最后返回合并后的结果数组。这个算法的时间复杂度是 O(m + n)，其中 m 和 n 分别是两个数组的长度，因为每个元素最多被访问一次。空间复杂度也是 O(m + n)，因为需要存储合并后的结果数组。

3.4 合并过程详细展示

if (arr1.isNotEmpty() && arr2.isNotEmpty()) {
    builder.appendLine("🔬 合并过程")
    val process = mutableListOf<String>()
    var i = 0
    var j = 0
    var step = 1

    while (i < arr1.size && j < arr2.size) {
        if (arr1[i] <= arr2[j]) {
            process.add("步骤 $step: 选择 arr1[$i]=${arr1[i]} (较小) → 结果: [${process.size + 1} 个元素]")
            i++
        } else {
            process.add("步骤 $step: 选择 arr2[$j]=${arr2[j]} (较小) → 结果: [${process.size + 1} 个元素]")
            j++
        }
        step++
    }
    // ... 处理剩余元素
}

代码解析：

这段代码实现了详细的合并过程输出，帮助用户理解算法是如何逐步合并两个数组的。首先检查两个数组是否都非空，只有在都非空时才显示详细过程，避免不必要的输出。

然后创建一个可变列表 process 用于存储每一步的描述信息。初始化两个指针 i 和 j 以及步骤计数器 step，这些变量的作用与核心合并函数中的相同。

接下来使用 while 循环模拟合并过程，逻辑与核心合并函数完全一致：比较两个指针指向的元素，选择较小的元素，记录这一步的操作信息，然后移动相应的指针。

在每一步中，构建详细的描述信息，包括步骤编号、选择的数组和索引、元素值、选择原因（较小）以及当前结果数组的元素数量。这种详细的输出对于教学和调试非常有用，用户可以清楚地看到每一步的选择过程。

例如，对于数组 [1, 3, 5] 和 [2, 4, 6]，输出可能是：

步骤 1: 选择 arr1[0]=1.0 (较小) → 结果: [1 个元素]
步骤 2: 选择 arr2[0]=2.0 (较小) → 结果: [2 个元素]
步骤 3: 选择 arr1[1]=3.0 (较小) → 结果: [3 个元素]
…

这种逐步展示帮助用户理解双指针归并算法的执行过程，特别是如何通过比较和选择逐步构建有序的结果数组。

3.5 统计信息输出

builder.appendLine("📊 统计信息")
builder.appendLine("总元素数: ${merged.size} (${arr1.size} + ${arr2.size})")

if (merged.isNotEmpty()) {
    val minVal = merged.minOrNull() ?: 0.0
    val maxVal = merged.maxOrNull() ?: 0.0
    val avgVal = merged.average()
    val median = if (merged.size % 2 == 0) {
        (merged[merged.size / 2 - 1] + merged[merged.size / 2]) / 2
    } else {
        merged[merged.size / 2]
    }

    builder.appendLine("最小值: $minVal")
    builder.appendLine("最大值: $maxVal")
    builder.appendLine("平均值: ${round2(avgVal)}")
    builder.appendLine("中位数: ${round2(median)}")
}

代码解析：

这段代码生成详细的统计信息，帮助用户了解合并后数组的特征。首先输出总元素数，显示合并后数组的长度以及两个原始数组的长度，使用格式 ${arr1.size} + ${arr2.size} 清晰地表示元素总数等于两个数组长度之和。

然后检查合并后的数组是否非空，只有非空时才计算统计信息，避免除零错误。计算最小值、最大值、平均值和中位数等统计指标。

最小值使用 minOrNull() 方法获取，如果数组为空返回 null，配合 Elvis 操作符 ?: 0.0 提供默认值。最大值使用相同的方式获取。

平均值使用 average() 方法直接计算，这是 Kotlin 集合提供的便捷方法，返回所有元素的平均值。

中位数的计算需要区分数组长度的奇偶性。如果数组长度为偶数，中位数是中间两个元素的平均值：(merged[merged.size / 2 - 1] + merged[merged.size / 2]) / 2。如果数组长度为奇数，中位数是中间元素：merged[merged.size / 2]。

最后使用 round2() 函数格式化平均值和中位数，保留两位小数，使输出更易读。这些统计信息提供了合并后数组的全面视图，帮助用户理解数据的分布特征。