第一周｜数组过滤器

后端语言里，数组在内存中使用的是一段连续的存储空间，对于合法索引支持随机访问。下面介绍数组过滤器的相关习题（一般要求只使用常数的额外空间）。算法基本思想是：

1. 顺序遍历数组元素
2. 检查是否符合条件
   2.1 符合条件 -> 留下
   2.2 不符合条件 -> 略过

遍历读取的过程，像是一个指针挥着衣袖，云彩依然在原地停留。“云彩”是（过滤前的）原始数据，虽然在访问过一次之后就没有利用价值了，但是它们依然无故地霸占着空间，白白地荒废着空间。所以，为何不把这些空间重新利用起来，新陈代谢、变废为宝呢？

要想达到这样高效的空间利用率，自然还需要另一个结果更新指针，它表示“当下一个符合条件的元素出现时，应当填写在哪个位置”，同时也表示“当前已经维护好的，（过滤后的）新生数据的长度”。

如果说读取指针的前行，是稳扎稳打、快马加鞭，那么写入指针的进展，就因依靠条件而相对缓慢。因此，这种多指针的思想，也被称为“快慢指针”。小试牛刀：

这两题之所以不需要额外开辟临时数组，是因为其更新数据的写入进度总是比原始数据的访问进度要慢，进而不存在读取脏数据导致结果紊乱或原始数据遗失的问题。不过，88.合并两个有序数组的处理方式，或许稍稍负责一些。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 最新数据-写指针
        int now = 0;
        int[] temp = new int[m + n];
        // 原始数据-读指针
        int i = 0, j = 0;
        // 条件：哪个更小填哪个，大的暂时先略过
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                temp[now++] = nums1[i++];
            } else {
                temp[now++] = nums2[j++];
            }
        }
        // 某一个数组触碰边界，另一个的元素直接挂载于尾部即可
        while (i < m) temp[now++] = nums1[i++];
        while (j < n) temp[now++] = nums2[j++];
        // 题目要求
        for (int k = 0; k < m + n; k++) {
            nums1[k] = temp[k];
        }
    }
}

在判断两个读指针所指向的数据孰大孰小，并把较小的一方填入时，如果不使用额外空间，冲突则是难以避免的。举例来说，此时此刻， \(nums_1\) 读指针指向的原始数据是3，如果直接更新于 \(nums_1\) 上，那么写指针就会领先读指针，把还没有访问的数据“吞”掉。

一个符合直觉的观察是， \(nums_1\) 后方有许多空位。倘若读写指针均倒序更新，写指针将天然落后读指针。于是可以直接对数组 \(nums_1\) 原地修改，不需要额外空间。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 最新数据-写指针
        int now = m + n - 1;
        // 原始数据-读指针
        int i = m - 1, j = n - 1;
        // 条件：哪个更大填哪个，小的暂时先略过
        while (i >= 0 && j >= 0) {
            if (nums1[i] <= nums2[j]) {
                nums1[now--] = nums2[j--];
            } else {
                nums1[now--] = nums1[i--];
            }
        }
        // 某一个数组触碰边界，另一个的元素直接挂载于尾部即可
        // while (i >=0 ) nums1[now--] = nums1[i--];
        while (j >= 0) nums1[now--] = nums2[j--];
    }
}