数组扁平化分析对比——复习

法1：不改变原数组

不改变原数组，返回一个结果数组。

Array.prototype.myFlat = function () {
    let result = [];
    this.forEach(element => {
        // element如果是数组，那么它也有该方法
        if (Array.isArray(element)) result.push(...element.myFlat());
        else result.push(element);
    })
    return result;
}

法2：改变原数组

直接在原数组上操作，无返回值。

第一手版本如下，常规思路，递归解包，最后原数组被拍平。

Array.prototype.flatten = function () {
    this.forEach((element, i) => {
        if (Array.isArray(element)) {
            element.myFlatten();// element如果是数组，那么它先将自己拍平
            this.splice(i, 1, ...element); // 递归行为：解包放回原位置，维度-1
        }
    })
}

而后发现这里有一个大问题，在forEach的过程中，将被遍历的数组长度修改，则会发生什么情况呢？

let a = [1, 2, 3];
let newItems = [5, 6, 7, 8];
a.forEach((item, index) => {
    if (index === 1) a.splice(1, 2, ...newItems);
    console.log({ item, index });
})
console.log(a);

// 结果为
{ item: 1, index: 0 }
{ item: 2, index: 1 }
{ item: -2, index: 2 }
{ item: -3, index: 3 }
{ item: 4, index: 4 }
{ item: 5, index: 5 }
[
  1, -1, -2, -3,
  4,  5,  6
]

显然这里有bug，forEach的遍历次数在一开始就被确定，不管后面数组会不会被修改。如果前面的数组扁平后，使数组长度变大，后面大于初试长度的元素就无法被访问到。继续修改，使用原生的for语句，每次重新读取数组长度。其二，如果当前子数组扁平后n，则可以确定从当前位置到后面n个元素一定是数字，所以可以进一步优化。

最后得到结果如下

Array.prototype.myFlatten = function () {
    for (let i = 0; i < this.length; ++i) {
        let element = this[i];
        if (Array.isArray(element)) {
            // element如果是数组，那么它也有该方法
            element.myFlatten(); //如果是数组，递归到底
            this.splice(i, 1, ...element); // 解包
            i += element.length - 2; // 后面n个一定都是数字，从当前位置，到最后一个位置，因为最后i还会加1次
        }
    }
}

// test
let testCase = [1, [2, 2, [1, [2, [3]]], 6, 7, [1, 2, 3]], [3, [4, 5]]];
testCase.myFlatten2();
console.log(testCase);

/*
[
  1, 2, 2, 1, 2, 3,
  6, 7, 1, 2, 3, 3,
  4, 5
]
*/

最后关于splice

splice(start, count, ...items)

第一个参数为起始下标，第二个参数为删除的个数，第3～n个参数为删除后，从起始位置start新添加的元素，若为空，则不添加元素。

vaakian / vaakian.github.io

数组扁平化分析对比——复习 #22

法1：不改变原数组

法2：改变原数组