LeetCode 1089. Duplicate Zeros

问题

问题描述：给出一个定长的正数数组 arr，将其中出现的每个 0 都重复一次，其他的元素右移。
注意不能写入超过原数组长度的元素，且原地修改 arr，不要返回任何值。

即在每个出现 0 的地方，再插入一个 0，其后的元素往右顺移，超出了数组长度的元素就不属于该数组了。

栗子1：

输入: [1,0,2,3,0,4,5,0]

对 0 重复添加后，变为 [1,0,0,2,3,0,0,4,5,0,0]
去除超过数组长度的部分，变为 [1,0,0,2,3,0,0,4]

栗子2：

输入：[1,2,3]

由于没有0，原数组不变：[1,2,3]

注意：

1. 1 <= arr.length <= 10000
2. 0 <= arr[i] <= 9

想看英文的戳这里：原题地址

解题思路

解法1

这种解法算是取巧，并不能体现出题目的原本用意。

思路为：遍历数组，遇到 0 即插入 0，最后将超出原数组的部分移除。

swift 代码如下：

// 100%
func duplicateZeros(_ arr: inout [Int]) {
    var i = arr.count - 1
    let count = arr.count
    while i >= 0 {
        if arr[i] == 0 {
            arr.insert(0, at: i)
        }
        
        i -= 1
    }
    
    // 删除超出原本 array 的部分。
    if arr.count > count {
        let range = Range.init(uncheckedBounds: (count, arr.count))
        
        arr.removeSubrange(range)
    }
}   

解法2

可从后往前，手动将 0 后面的数字往右移，在空出的位置填上 0 即可。比如 arr[i] = 0，只需要将 [i + 1 , arr.count - 2] 后移。

但当 0 越在前面或者 0 个数多，移动次数会越多，所以时间复杂度会高一些。

代码

swift 代码

// 20%
func duplicateZeros2(_ arr: inout [Int]) {
    var i = arr.count - 1
    
    // 从后往前，遍历 0
    while i >= 0 {
        if arr[i] == 0 {
            // 后移 [i+1, arr.count-2]
            var k = arr.count - 2
            while k >= i + 1 {
                arr[k + 1] = arr[k]
                k -= 1
            }
            
            // 填上0
            arr[k + 1] = 0
        }
        i -= 1
    }    
}

解法3

该解法算是真正意义上的解法。

思路：从后往前，跳过超出数组长度的元素，计算出每个元素应该放的位置，如果遇到 0，则往前再放一个 0。

假设原数组长度为 n。首先遍历数组，计算出加上重复 0 之后的数组总长度 m。令j = m，从后往前遍历数组，j 同时减 1。当 j >= n 时，原数组中的元素是不需要的，可跳过。

当 j < n时，分两步进行。

1. 先从原数组中取出元素，放到 j 位置。
2. 判断该元素是否为 0，如果为 0，则j 前移，j -= 1， 再添加一个 0 到 j 的位置,。

只需要遍历 2 次数组，即可完成。

图解

可能文字有些绕，下面是步骤图解。

1. i = 5, j = 7，跳过

QQ20190621-1@2x.png

2. i = 4, j = 6，第一步跳过。注意 a[4] = 0，所以需再判断前一个位置是否满足条件，j = 5 是最后一个位置，可填入 a[5] = 0

QQ20190621-2@2x.png

3. i = 3, j = 4，可填入 a[4] = 6

QQ20190621-3@2x.png

4. i = 2, a[2] = 0，第一步可填入 a[3] = 0，第二步也可填入 a[2] = 0

QQ20190621-4@2x.png

5. i = 1，a[1] = 3，j = 1，填入 a[1] = 3

QQ20190621-5@2x.png

6. i = 0, a[1] = 1, j = 0，可填入 a[0] = 1

QQ20190621-6@2x.png

代码

swift 代码

func duplicateZeros3(_ arr: inout [Int]) {
    let n = arr.count
    var i = 0
    var j = 0
    
    // j 表示增加 0 后的数组总长度
    while i < n {
        if arr[i] == 0 {
            j += 1
        }
        
        i += 1
        j += 1
    }
    
    // 从后遍历
    i = n - 1
    while i >= 0 {
        
        // 如果 j 在原数组范围内，则赋值，相当于在 i 中跳过不满足条件的值
        j -= 1
        if j < n, j >= 0 {
            arr[j] = arr[i]
        }
        
        // 如果 = 0，再添加一个0
        if arr[i] == 0 {
            j -= 1
            if j < n, j >= 0 {
                arr[j] = 0
            }
        }
        
        i -= 1
    }
}