欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net

摘要

移除元素工具实现了移除数组中所有等于目标值的元素，返回移除后数组的新长度，并修改原数组的功能。本文详细解析了输入解析、双指针法、从后向前移除法等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个数组和一个目标值，移除数组中所有等于目标值的元素，并返回移除后数组的新长度。要求原地修改数组。

示例：

• 数组：[3, 2, 2, 3]
• 目标值：3
• 结果：新长度 2，数组变为 [2, 2]

1.2 应用场景

• 数组过滤
• 数据清洗
• 就地修改数组
• 算法竞赛

2. 核心算法原理

2.1 双指针法（快慢指针）

使用快指针遍历数组，慢指针记录保留元素的位置。当快指针指向的元素不等于目标值时，将其复制到慢指针位置。时间复杂度 O(n)，空间复杂度 O(1)。

2.2 从后向前移除法

从数组末尾向前遍历，遇到目标值就移除。时间复杂度 O(n²)（每次移除需要移动元素），空间复杂度 O(1)。

3. 代码实现详细解析

3.1 输入解析模块

var nums: List<Int>? = null
var targetValue = 0

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("nums=", ignoreCase = true) -> {
                val valuesStr = line.substringAfter("=").trim()
                try {
                    nums = valuesStr.split(",")
                        .map { it.trim() }
                        .filter { it.isNotEmpty() }
                        .map { it.toInt() }
                } catch (e: Exception) {
                    nums = null
                }
            }
            line.startsWith("val=", ignoreCase = true) -> {
                try {
                    targetValue = line.substringAfter("=").trim().toInt()
                } catch (e: Exception) {
                    targetValue = 0
                }
            }
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持从输入字符串中提取数组和目标值。首先声明两个变量：nums 是一个可空整数列表，用于存储解析后的数组；targetValue 是目标值，初始值为 0。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。

在 forEach 循环中，使用 when 表达式进行模式匹配。第一个分支处理 nums= 格式的输入：提取等号后面的部分作为数组字符串，然后使用 split(",") 按逗号分割，map { it.trim() } 去除空白字符，filter { it.isNotEmpty() } 过滤空元素，map { it.toInt() } 转换为整数。使用 try-catch 块捕获可能的异常，确保程序的健壮性。

第二个分支处理 val= 格式的输入：提取等号后面的部分并转换为整数。如果解析失败，保持目标值为 0。

如果解析后数组为 null，则尝试直接解析输入：将第一行按逗号分割并转换为整数数组，第二行作为目标值。这种备选方案提高了输入格式的灵活性。

3.2 双指针法（快慢指针）实现

fun removeElementTwoPointer(nums: MutableList<Int>, `val`: Int): Pair<Int, List<Int>> {
    var slow = 0

    for (fast in nums.indices) {
        if (nums[fast] != `val`) {
            nums[slow] = nums[fast]
            slow++
        }
    }

    return Pair(slow, nums.take(slow))
}

代码解析：

这是双指针法（快慢指针）的核心实现，通过两个指针高效地移除目标元素。函数接受一个可变列表和目标值作为参数，返回移除后的新长度和保留的元素列表。

首先初始化慢指针 slow = 0，慢指针指向下一个应该放置保留元素的位置。

然后使用快指针 fast 遍历数组的所有元素。在循环内部，检查快指针指向的元素是否不等于目标值。如果 nums[fast] != val，说明这个元素应该被保留。

将快指针指向的元素复制到慢指针位置：nums[slow] = nums[fast]。这会将保留的元素移动到数组的前面，覆盖掉原来的位置（如果慢指针小于快指针的话）。

然后将慢指针向右移动：slow++，指向下一个应该放置保留元素的位置。

如果快指针指向的元素等于目标值，则不做任何操作，直接跳过这个元素。快指针会继续向右移动（通过 for 循环），但慢指针保持不变，这样目标值就不会被复制到新位置。

循环结束后，慢指针的值就是移除后数组的新长度，因为慢指针记录的是保留元素的数量。所有保留的元素都在数组的前 slow 个位置。

最后返回新长度和保留的元素列表。使用 nums.take(slow) 获取前 slow 个元素，这是保留的元素。

这个算法的时间复杂度是 O(n)，其中 n 是数组的长度，因为只需要遍历数组一次。空间复杂度是 O(1)，因为只使用了两个指针变量，没有使用额外的空间。这是一种原地修改的算法，非常高效。

3.3 从后向前移除法实现

fun removeElementBackward(nums: MutableList<Int>, `val`: Int): Pair<Int, List<Int>> {
    var i = nums.size - 1
    while (i >= 0) {
        if (nums[i] == `val`) {
            nums.removeAt(i)
        }
        i--
    }
    return Pair(nums.size, nums)
}

代码解析：

这是从后向前移除法的实现，通过从数组末尾向前遍历来移除目标元素。函数接受一个可变列表和目标值作为参数，返回移除后的新长度和修改后的数组。

首先初始化索引 i = nums.size - 1，指向数组的最后一个元素。

然后使用 while 循环从后向前遍历数组，条件是 i >= 0，即索引还没有越界。

在循环内部，检查当前索引位置的元素是否等于目标值。如果 nums[i] == val，说明这个元素应该被移除。使用 nums.removeAt(i) 移除该位置的元素。removeAt 方法会移除指定位置的元素，并将后面的元素向前移动，填补空位。

然后将索引减 1（i--），继续处理前一个元素。注意这里无论是否移除了元素，索引都会减 1。这是因为如果移除了元素，后面的元素会向前移动，原来 i - 1 位置的元素现在在 i - 1 位置；如果没有移除元素，索引也应该减 1 继续向前遍历。

循环结束后，数组中的所有目标值都已被移除。返回数组的新长度（nums.size）和修改后的数组。

这个算法的时间复杂度是 O(n²)，其中 n 是数组的长度。虽然遍历是 O(n)，但每次调用 removeAt 都需要移动后面的元素，最坏情况下需要移动 O(n) 次，所以总体时间复杂度是 O(n²)。空间复杂度是 O(1)，因为只使用了固定数量的变量。

虽然这个算法的时间复杂度较高，但它的实现非常简单直观，容易理解。在实际应用中，如果数组较小或者目标值很少，这种方法也是可以接受的。

3.4 双指针法移除过程分析

for (fast in mutableNums.indices) {
    builder.appendLine("步骤 ${fast + 1}:")
    builder.appendLine("  快指针位置: $fast (值: ${mutableNums[fast]})")
    builder.appendLine("  慢指针位置: $slow")

    if (mutableNums[fast] != targetValue) {
        if (slow != fast) {
            builder.appendLine("  移动: nums[$slow] = nums[$fast] = ${mutableNums[fast]}")
            mutableNums[slow] = mutableNums[fast]
        } else {
            builder.appendLine("  保留: 元素不等于目标值，无需移动")
        }
        slow++
    } else {
        builder.appendLine("  跳过: 元素等于目标值，不复制")
    }

    builder.appendLine("  当前状态: [${mutableNums.take(slow).joinToString(", ")}] + [${mutableNums.drop(slow).take(mutableNums.size - slow).joinToString(", ")}]")
}

代码解析：

这段代码实现了详细的移除过程分析，帮助用户理解双指针法是如何逐步移除目标元素的。首先遍历数组的每个位置，使用快指针 fast 指向当前位置。

在每一步中，输出当前快指针的位置和对应的值，以及慢指针的位置。然后检查快指针指向的元素是否不等于目标值。

如果元素不等于目标值，说明应该被保留。检查慢指针和快指针是否在同一个位置。如果不在同一位置（slow != fast），说明需要将元素从快指针位置复制到慢指针位置，输出移动操作。如果在同一位置，说明元素已经在正确的位置，无需移动，输出保留信息。

然后慢指针向右移动（slow++），指向下一个应该放置保留元素的位置。

如果元素等于目标值，说明应该被移除。输出跳过信息，不做任何操作，慢指针保持不变。

最后输出当前的状态，显示已经保留的元素（前 slow 个元素）和剩余的元素。这种详细的输出帮助用户理解算法的工作原理，特别是快慢指针是如何协调工作的。

4. 算法复杂度分析

4.1 时间复杂度

• 双指针法：O(n)，只需要遍历数组一次
• 从后向前移除法：O(n²)，每次移除需要移动元素
• 总体时间复杂度：O(n)（使用双指针法）

4.2 空间复杂度

• 双指针法：O(1)，只使用固定数量的变量
• 从后向前移除法：O(1)，只使用固定数量的变量
• 总体空间复杂度：O(1)

5. 算法优化建议

5.1 双指针法优化

双指针法已经是时间最优的算法，时间复杂度为 O(n)，无法进一步优化。

5.2 空间优化

两种方法都是原地修改数组，空间复杂度已经是 O(1)，无法进一步优化。

5.3 边界条件处理

代码已经处理了各种边界情况：空数组、目标值不存在、所有元素都是目标值等情况。

6. 应用场景扩展

1. 数组过滤：从数组中过滤掉特定值的元素
2. 数据清洗：清洗数据中不需要的值
3. 就地修改数组：在不创建新数组的情况下修改数组
4. 算法竞赛：LeetCode 等平台的经典问题
5. 扩展问题：移除多个值、条件移除等变体

7. 总结

移除元素工具实现了两种移除方法，核心要点：

1. 双指针法：时间复杂度 O(n)，使用快慢指针，高效地移除目标元素
2. 从后向前移除法：实现简单，但时间复杂度 O(n²)
3. 原地修改：两种方法都支持原地修改数组，空间复杂度 O(1)
4. 快慢指针思想：快指针遍历，慢指针记录保留位置，是数组操作的重要技巧

通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如数组过滤、数据清洗、就地修改等场景。双指针法的思想也可以扩展到其他类似的数组操作问题中。