Java&C++题解与拓展——leetcode1089.复写零【么的新知识】

• 题目要求
• 思路一：双指针
• • Java
  • C++
• 思路二：容器插入
• • C++
  • Rust
• 总结

• 数组长度是固定的，所以数组末尾会有几位被吞掉，那就先找到结果最后一位原来的下标，然后依次赋给末尾，有零就补零。
• 双指针一个从结果末尾开始，一个从原数组末尾开始，向前移动，后者永远不会超越前者，所以当前者越过 0 0 0，说明遍历结束。

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length, i = 0, j = 0;
        // 找能留下的最后一位i
        while (j < n) {
            if (arr[i] == 0)
                j++;
            i++;
            j++;
        }
        i--;
        j--;
        // 直接赋值覆盖
        while (i >= 0) {
            if (j < n)
                arr[j] = arr[i];
            if (arr[i] == 0)
                arr[--j] = 0;
            i--;
            j--;
        }
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
public:
    void duplicateZeros(vector& arr) {
        int n = arr.size(), i = 0, j = 0;
        // 找能留下的最后一位i
        while (j < n) {
            if (arr[i] == 0)
                j++;
            i++;
            j++;
        }
        i--;
        j--;
        // 直接赋值覆盖
        while (i >= 0) {
            if (j < n)
                arr[j] = arr[i];
            if (arr[i] == 0)
                arr[--j] = 0;
            i--;
            j--;
        }
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

• 这里属于是流氓解法了……
• 在某些语言中，用容器表示变长数组，容器是可以指定位置插入数据的呀，那就直接插个 0 0 0进去，每次插入之后记得弹一位出去保证数组长度就好了。

class Solution {
public:
    void duplicateZeros(vector& arr) {
        for (int i = arr.size() - 1; i >= 0; i--) {
            if (arr[i] == 0) {
                arr.insert(arr.begin() + i, 0);
                arr.pop_back();
            }
        }
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

impl Solution {
    pub fn duplicate_zeros(arr: &mut Vec) {
        let n = arr.len();
        for i in (0..n - 1).rev() {
            if arr[i] == 0 {
                arr.insert(i, 0);
                arr.pop();
            }
        }
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

是我最爱的双指针模拟了，正反两次遍历解决。

顺便get了rust数组（容器）的灵活操作在本题中带来的便利。【强调本题，因为其他题有的时候反而是麻烦】