Kotlin原地复制数组中的零：算法逻辑错误排查与修正求助

问题描述 #

给定固定长度整数数组arr，需原地复制每个出现的零，将剩余元素右移，超出数组长度的元素丢弃，且不能返回值或复制数组。

示例 #

• 输入[1,0,2,3,0,4,5,0] → 输出[1,0,0,2,3,0,0,4]
• 输入[1,2,3] → 输出[1,2,3]

初始代码错误分析 #

用户最初的代码：

class Solution {
    fun duplicateZeros(arr: IntArray): Unit {
        arr.forEachIndexed { index, value ->
            if(value == 0 && ((arr.size - 1) != index)) {
                arr[index + 1] = 0
            }
        }
    }
}

错误原因：

• 从左到右遍历遇到零时直接覆盖下一个元素，导致后续未处理的原始值被提前覆盖。例如第一个零会将下一个位置设为零，下一次遍历到这个新零又会继续覆盖，最终所有后续元素都被置零。
• 未实现元素右移逻辑，只是简单覆盖，丢失了原数组的有效数据。

新版代码问题排查 #

用户更新后的代码采用了从右往左复制的思路，但长测试用例失败，核心问题在于：

1. extraSpace计算逻辑错误：原条件i < nums.lastIndex - extraSpace无法准确判断哪些零可以被复制，导致计数偏差。
2. 边界处理缺失：未考虑最后一个零无法被复制的情况，导致多写入一个零。

修正后的代码 #

fun main() {
    val nums = longTestCase()
    val n = nums.size
    var count = 0
    var i = 0

    // 计算可被复制的零的数量
    while (i + count < n) {
        if (nums[i] == 0) {
            count++
        }
        i++
    }

    // 处理边界：最后一个零无法完全复制的情况
    if (i + count > n) {
        nums[n-1] = 0
        count--
        i--
    }

    // 从右往左复制元素
    var temp = n - 1
    i-- // 定位到原数组最后一个有效元素

    while (temp >= 0 && count > 0) {
        if (nums[i] == 0) {
            nums[temp] = 0
            temp--
            nums[temp] = 0
            temp--
            count--
        } else {
            nums[temp] = nums[i]
            temp--
        }
        i--
    }

    // 复制剩余非零元素
    while (temp >=0) {
        nums[temp] = nums[i]
        temp--
        i--
    }

    nums.forEach { print("$it ") }
}

private fun longTestCase(): IntArray {
    return intArrayOf(
        9,9,9,4,8,0,0,3,7,2,0,0,0,0,9,1,0,0,1,1,0,5,6,3,1,6,0,0,2,3,4,7,0,3,9,3,6,5,8,9,1,1,3,2,0,0,7,3,3,0,5,7,0,8,1,9,6,3,0,8,8,8,8,0,0,5,0,0,0,3,7,7,7,7,5,1,0,0,8,0,0
    )
}

关键修复点 #

1. 准确计数可复制的零：通过i + count < n判断，确保复制后的总长度不超过数组边界，得到正确的count（需要复制的零的数量）。
2. 边界处理：若最后一个零无法被复制（会超出数组长度），单独将数组最后一位设为零，并调整计数和指针。
3. 从右往左复制：避免覆盖未处理的原始元素，遇到零时写入两个零并减少计数，非零元素直接复制。
4. 剩余元素处理：完成所有零的复制后，将剩余的非零元素复制到对应位置。

内容的提问来源于stack exchange，提问作者Compose Learner