【力扣】2626. 数组归约运算——认识循环

【力扣】2626. 数组归约运算——认识循环

题目

给定一个整数数组 nums、一个 reducer 函数 fn 和一个初始值 init，返回通过依次对数组的每个元素执行 fn 函数得到的最终结果。

通过以下操作实现这个结果：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 。

提示：

• 0 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• 0 <= init <= 1000

解决方案

综述

本问题要求你编写一个基于 回调 函数的输出执行缩减变换的函数。除了map和filter之外，它是 JavaScript 中最常用和重要的函数之一。

首先，建议你阅读关于map和filter的内容，因为它们当中包含了相关的讨论。

Reduce 的用途

Reduce 遍历数组中的每个值，并以某种方式将每个值合并到一个累加器变量中。第一个参数是一个回调函数，它接受当前的accumulator 值和每个数组元素，并返回一个新的accumulator值。第二个参数是accumulator的初始值。在遍历整个数组后，将返回accumulator的最终值。

这是一个简单的操作，但在可以执行的转换类型上非常多样。在 Array.map 和Array.filter无法解决问题时你可以将其用于几乎所有数组迭代。

以下示例使用内置的Array.reduce方法。

求和数组中的值

Reduce 的经典用例是将数组中的所有值相加。

const nums = [1, 2, 3];
const sum = nums.reduce((accumulator, val) => accumulator + val, 0);
console.log(sum); // 6

你还可以基于某个属性对值求和，稍作修改即可。

const nums = [{x: 1}, {x: 2}, {x: 3}];
const sum = nums.reduce((accumulator, val) => accumulator + val.x, 0);
console.log(sum); // 6

按键索引数组

在编程中非常常见的任务形式是将一组数据按某个键进行索引。这样，可以通过 O(1) 的时间复杂度访问数据的键。

const groceries = [
  { id: 173, name: "Soup" }, 
  { id: 964, name: "Apple" },
  { id: 535, name: "Cheese" }
];

const indexedGroceries = groceries.reduce((accumulator, val) => {
  accumulator[val.id] = val;
  return accumulator;
}, {});

console.log(indexedGroceries);
/**
 * {
 *   "173": { id: 173, name: "Soup" },
 *   "964": { id: 964, name: "Apple" },
 *   "535": { id: 535, name: "Cheese" },
 * }
 */

请注意，开发人员常犯的一个性能错误是在每次数组迭代时创建累加器的克隆，即 return { ...accumulator, [val.id]: val };。这将导致该算法的复杂度为 O(n2)。

结合 Filter 和 Map

有时候需要将 .filter() 和.map()链接在一起，以删除数组中的元素并进行转换。问题在于这种方法效率较低，因为这种数组方法会在只需要一个数组的情况下创建两个数组。
你可以将 filter 和 map 合并为单个 reduce，以提高性能。

const groceries = [
  { id: 173, name: "Soup" }, 
  { id: 964, name: "Apple" },
  { id: 535, name: "Cheese" }
];

/** 使用 filter 和 map */
var names = groceries
  .filter(item => item.id > 500)
  .map(item => item.name)

/** 使用 reduce */
var names = groceries.reduce((accumulator, val) => {
  if (val.id > 500) {
    accumulator.push(val.name);
  }
  return accumulator;
}, []);

console.log(names); // ["Apple", "Cheese"]

内置 Array.reduce

这个问题要求你重新实现Array.reduce方法，它是 JavaScript 中最常用的数组方法之一。但是，你的实现会与标准库有四个小差异。

1. Array.reduce 是数组原型上的方法。这个实现是一个函数，接受数组作为第一个参数。
2. 传递给 Array.reduce 的回调函数接受额外的两个参数。第三个参数是数组的 currentIndex。第四个参数是对原始数组的引用。
3. Array.reduce 可选地允许你不传递initialValue 作为第二个参数。如果数组中没有元素，将会抛出一个错误。否则，initialValue将被视为数组中的第一个元素，并从索引 1 开始迭代。
4. Array.reduce 处理稀疏数组。例如，如果你编写代码 let arr = Array(100); arr[1] = 10;，Array.reduce 将只会查看索引 1，并会忽略空索引。这相当于在调用reduce()之前过滤掉所有空值。

方法 1：使用 For…of 循环

JavaScript 具有简单的语法，允许你遍历 可迭代 对象的每个元素。Set、Map 和 String 都是可迭代对象的示例。

var reduce = function(arr, fn, initialVal) {
  let accumulator = initialVal;
  for (const element of arr) {
      accumulator = fn(accumulator, element);
  }
  return accumulator;
};

方法 2：使用 Array.forEach 循环

JavaScript 数组具有用于遍历每个元素的内置方法。通常之所以优先选择它而不是普通的for循环，是因为它将实际值作为回调的第一个参数提供给回调函数，从而可能节省一行代码。

var reduce = function(arr, fn, initialVal) {
  let accumulator = initialVal;
  arr.forEach((element) => {
    accumulator = fn(accumulator, element);
  });
  return accumulator;
};

方法 3：使用 For…in 循环

For...in 循环更常用于遍历对象的键。但是，它们也可以用于遍历数组的索引。这种方法的显著特点是，它通过忽略空索引来考虑稀疏数组。例如，如果你编写了 let arr = Array(100); arr[1] = 10;，这种方法会将数组视为只有一个元素。

var reduce = function(arr, fn, initialVal) {
  let accumulator = initialVal;
  for (const index in arr) {
    accumulator = fn(accumulator, arr[index]);
  } 
  return accumulator;
};

复杂度分析

以下分析适用于所有这些方法。假设 N 是输入数组的长度。

时间复杂度：O(N)。算法会遍历所有元素。
空间复杂度取决于提供的回调函数。例如，对数组中的元素求和是空间复杂度为 O(1) 的操作。而在最坏的情况下，过滤数组的空间复杂度为 O(N)。