# 基本数组转换

# 转换数组中的每个元素

编写一个函数，这个函数接收一个整数数组 arr 和一个映射函数 fn ，通过该映射函数返回一个新的数组。

返回数组的创建语句应为 returnedArray[i] = fn(arr[i], i) 。

请你在不使用内置方法 Array.map 的前提下解决这个问题。

# 示例 1:

输入：arr = [1,2,3], fn = function plusone(n) { return n + 1; }
输出：[2,3,4]
解释：
const newArray = map(arr, plusone); // [2,3,4]
此映射函数返回值是将数组中每个元素的值加 1。

# 示例 2:

输入：arr = [1,2,3], fn = function plusI(n, i) { return n + i; }
输出：[1,3,5]
解释：此映射函数返回值根据输入数组索引增加每个值。

# 示例 3:

输入：arr = [10,20,30], fn = function constant() { return 42; }
输出：[42,42,42]
解释：此映射函数返回值恒为 42。

# 题解

# 方法 1：将值写入初始为空的数组

在 JavaScript 中，你可以读取和写入不在范围 [0, arr.length) 内的索引。与普通对象一样，访问不存在的索引会返回 undefined。通常不鼓励写入不存在的索引，因为除了令人困惑之外，它还会导致性能慢且不可预测。这种方法对 500 万个元素需要约 250 毫秒。

var map = function (arr, fn) {
    const newArr = [];
    for (let i = 0; i < arr.length; ++i) {
        newArr[i] = fn(arr[i], i);
    }
    return newArr;
};

# 方法 2：使用 for...in 循环

for...in 循环更常用于遍历对象的键。但是，它们也可以用于遍历数组的索引。这种方法之所以引人注目，是因为它遵守稀疏数组。例如，如果你编写了 let arr = Array(100); arr[1] = 10;，这种方法只会转换一个元素。这种方法对 500 万个元素需要约 1000 毫秒。值得注意的是，这是最接近内置 Array.map 工作方式的方法。因为 Array.map 需要处理稀疏数组，所以通常比一个假设数组不稀疏的最佳自定义实现慢几倍。

var map = function (arr, fn) {
    const newArr = new Array(arr.length);
    for (const i in arr) {
        newArr[i] = fn(arr[i], Number(i));
    }
    return newArr;
}

# 方法 3：将值推入数组

JavaScript 数组的命名会让人困惑，因为传统上数组具有固定大小。然而，在 JavaScript 中，数组可以附加元素，平均时间复杂度为 O(1) O(1)O(1)。你可以通过逐个将每个元素附加到末尾来构建一个转换后的数组。这种方法对 500 万个元素需要约 200 毫秒。

var map = function (arr, fn) {
    const newArr = [];
    for (let i = 0; i < arr.length; ++i) {
        newArr.push(fn(arr[i], i));
    }
    return newArr;
};

# 方法 4：预先分配内存

你可以使用 new Array(len)构造函数创建一个具有一些长度的空数组。 请注意，内存已分配，但数组实际上不包含任何元素。与将元素附加到数组末尾相比，这种技术性能更好。 这是因为每 当你将值推入数组时，数组可能没有分配足够的内存，因此需要重新分配内存。 这是一个昂贵的操作。初始化内存可以获得更好的性能。这种方法对 500 万个元素需要约 40 毫秒。

var map = function (arr, fn) {
    const newArr = new Array(arr.length);
    for (let i = 0; i < arr.length; ++i) {
        newArr[i] = fn(arr[i], i);
    }
    return newArr;
};

# 方法 5：32 位整数数组

JavaScript 允许你使用类型化数组（typed arrays）。这不像普通的 JavaScript 数组，因为它们只允许特定的数据类型，并且它们的大小不能被改变。这些是在想要以节省内存的方式存储大量数据时有用的工具 。传统数组可能会占用大量内存，因为它们不是固定大小的，可以存储任意数据。这种方法对 500 万个元素需要约 20 毫秒。

var map = function (arr, fn) {
    const newArr = new Int32Array(arr.length);
    for (let i = 0; i < arr.length; ++i) {
        newArr[i] = fn(arr[i], i);
    }
    return newArr;
};

# 方法 6：内存中的转换

为了实现最佳性能，你可以简单地重用已分配给第一个数组的内存。需要注意的是，通常不鼓励函数修改传递给它的值。这可能导致用户意外的副作用和错误。内置的 Array.map 不会修改原始数组。这种方法对 500 万个元素需要约 10 毫秒。

var map = function (arr, fn) {
    for (let i = 0; i < arr.length; ++i) {
        arr[i] = fn(arr[i], i);
    }
    return arr;
};

# 过滤数组中的元素

给定一个整数数组 arr 和一个过滤函数 fn，并返回一个过滤后的数组 filteredArr 。

fn 函数接受一个或两个参数：

arr[i] - arr 中的数字
i - arr[i] 的索引
filteredArr 应该只包含使表达式 fn(arr[i], i) 的值为真值的 arr 中的元素。真值是指 Boolean(value) 返回参数为 true 的值。

请在不使用内置的 Array.filter 方法的情况下解决该问题。

# 示例 1：

输入：arr = [0,10,20,30], fn = function greaterThan10(n) { return n > 10; }
输出： [20,30]
解释：
const newArray = filter(arr, fn); // [20, 30]
过滤函数过滤掉不大于 10 的值

# 示例 2：

输入：arr = [1,2,3], fn = function firstIndex(n, i) { return i === 0; }
输出：[1]
解释：
过滤函数 fn 也可以接受每个元素的索引
在这种情况下，过滤函数删除索引不为 0 的元素

# 示例 3：

输入：arr = [-2,-1,0,1,2], fn = function plusOne(n) { return n + 1 }
输出：[-2,0,1,2]
解释：
像 0 这样的假值应被过滤掉

# 题解

# 方法 1：将值推入新数组

你可以创建一个新数组，将满足 fn(arr[i], i)返回真值的所有值都推入其中。这是通过迭代原始数组中的每个元素来完成的。

注意

将元素推入数组可能是一个慢操作。这是因为数组可能没有足够的空间来存储新元素

var filter = function (arr, fn) {
    const newArr = [];
    for (let i = 0; i < arr.length; ++i) {
        if (fn(arr[i], i)) {
            newArr.push(arr[i]);
        }
    }
    return newArr;
};

# 方法 2：使用 For...in 循环

For...in 循环更常用于遍历对象的键。但是，它们也可以用于遍历数组的索引。这种方法之所以引人注目，是因为它优先稀疏数组 ，省略空索引。例如，如果你编写了 let arr = Array(100); arr[1] = 10;，这种方法只会对单个元素应用过滤，并会自动删除所有空值。

值得注意的是，这是最接近内置 Array.filter 工作方式的方法。因为 Array.filter 需要处理稀疏数组，所以通常比一个假设数组不稀疏的最佳自定义实现更慢。另一个需要注意的是，由于 For...in 循环包括对象原型上的键，因此通常最好使用 Object.keys()。

var filter = function (arr, fn) {
    const newArr = [];
    for (const stringIndex in arr) {
        const i = Number(stringIndex);
        if (fn(arr[i], i)) {
            newArr.push(arr[i]);
        }
    }
    return newArr;
};

# 方法 3：预分配内存

将元素推入数组可能是一个慢操作。这是因为数组可能没有足够的空间来存储新元素，因此需要调整大小。通过使用 new Array(size) 初始化数组，可以避免这些高代价的调整大小操作。最后，我们将通过从数组末尾弹出来删除空元素。请注意，当原始数组中移除的元素较少时，此算法的性能最佳。

var filter = function (arr, fn) {
    let size = 0;
    const newArr = new Array(arr.length);
    for (let i = 0; i < arr.length; ++i) {
        if (fn(arr[i], i)) {
            newArr[size] = arr[i];
            size++;
        }
    }
    // 确保新数组的长度为 size
    while (newArr.length > size) {
        newArr.pop();
    }
    return newArr
};

# 方法 4：原地执行操作

这个方法类似于方法 3 ，但利用了输入数组的内存，避免了创建新数组的成本。需要注意的是，尽管这个解决方案是有效的，但通常不建议修改传递给函数的参数。这是因为函数的用户可能不希望他们的数组被修改，这可能导致 bug。请注意，内置的 Array.filter 不会修改输入数组。

var filter = function (arr, fn) {
    let size = 0;
    for (let i = 0; i < arr.length; ++i) {
        if (fn(arr[i], i)) {
            arr[size] = arr[i];
            size++;
        }
    }
    // 确保新数组的长度为 size
    while (arr.length > size) {
        arr.pop();
    }
    return arr
};

# 性能分析

方法 2（for...in）和方法 5（内置）最慢，因为它们处理稀疏数组的情况。
方法 1（推入）在大多数元素被删除时是最快的。这是因为在这些情况下，昂贵的推入操作很少发生。
方法 3（预分配内存）和方法 4（原地执行）在删除很少的元素时是最快的。这是因为在这些情况下，弹出操作很少发生。方法 4 比方法 3 更快，因为不需要创建初始数组。

# 数组归约运算

请你编写一个函数，它的参数为一个整数数组 nums 、一个计算函数 fn 和初始值init 。返回一个数组归约后的值。

你可以定义一个数组归约后的值，然后应用以下操作： val = fn(init, nums[0]) ， val = fn(val, nums[1]) ， val = fn(val, nums[2]) ，... 直到数组中的每个元素都被处理完毕。返回 val 的最终值。

如果数组的长度为 0，它应该返回 init 的值。

请你在不使用内置数组方法的 Array.reduce 前提下解决这个问题。

# 示例 1：

输入：
nums = [1,2,3,4]
fn = function sum(accum, curr) { return accum + curr; }
init = 0
输出：10

解释：初始值为 init=0 。
(0) + nums[0] = 1
(1) + nums[1] = 3
(3) + nums[2] = 6
(6) + nums[3] = 10
Val 最终值为 10。

# 示例 2：

输入：

nums = [1,2,3,4]
fn = function sum(accum, curr) { return accum + curr * curr; }
init = 100

输出：130

解释：
初始值为 init=100 。
(100) + nums[0]^2 = 101
(101) + nums[1]^2 = 105
(105) + nums[2]^2 = 114
(114) + nums[3]^2 = 130
Val 最终值为 130。

# 示例3:

输入：
nums = []
fn = function sum(accum, curr) { return 0; }
init = 25
输出：25
解释：这是一个空数组，所以返回 init 。

# 题解

const reduceArr = (arr, fn, init = 0) => {
    let pre = init;
    for (let i = 0; i < arr.length; i++) {
        pre = fn(pre, arr[i]);
    }
    return pre;
};
console.log(
    "结果",
    reduceArr([1, 2, 3, 4], (pre, cur) => pre + cur)
);
console.log(
    "结果",
    reduceArr([1, 2, 3, 4], (pre, cur) => pre + cur * cur, 100)
);
console.log(
    "结果",
    reduceArr([], (pre, cur) => pre * cur, 15)
);

← 闭包函数转换 →