1、arr.reduce详解

array.reduce(function (total, currentValue, currentIndex, arr), initialValue):

  • initialValue为传递给回调函数的total初始值
  • function中若干参数的解释如下:
    • total: 初始值initialValue或上一次迭代时fun的返回值
    • currentValue: 当前值
    • currentIndex: 当前索引 => 可省略
    • arr: 要累加的arr非空数组 => 可省略

注意: 当 initialValue 的值为空的，也就是没有初始值时，函数第一次累加的 total 将会是 arr 的第一个元素，此时currentindex 的值为 1。

2、数组中出现最多的元素

有一道算法题是这样的：让你编程找到数组中出现次数最多的元素, 该数组中的元素都为数字, 例如输入为[2, 2, 1, 1, 1, 2, 2], 输出为2。备注：这里假设次数最多的元素是存在的, 不需要讨论任何特殊情况。

无脑写法

无脑写法如下(时间复杂度O(n) 空间复杂度: O(n)):

const findMostElement = (arr) => {
  // 遍历统计每个元素出现的次数
  let temp = (new Array(arr.length)).fill(0);
  arr.forEach((item) => {
    temp[item] = temp[item] + 1;
  });
  // 找到出现最多的元素
  let res = 0;
  let count = 0;
  for (let i = 0; i < temp.length; i++) {
    if (temp[i] > count) {
      count = temp[i];
      res = i;
    }
  }

  return res;
};

console.log(findMostElement([2, 2, 1, 1, 1, 2, 2]));    // 2
console.log(findMostElement([2, 2, 2, 2, 2, 2, 2]));    // 2
console.log(findMostElement([1, 2, 3, 4, 5, 6, 6]));    // 6

基于arr.reduce的实现

JavaScript的数组有一个reduce方法, 可以对数组做迭代处理, 例如累加求和、计算每个元素出现的次数等。 下面是计算每个元素出现的次数的代码:

const names = ["Alice", "Bob", "Tiff", "Bruce", "Alice"];
const countedNames = names.reduce(function (allNames, name) {
  if (name in allNames) {
    allNames[name]++;
  } else {
    allNames[name] = 1;
  }
  return allNames;
}, {});
console.log(countedNames); // { 'Alice': 2, 'Bob': 1, 'Tiff': 1, 'Bruce': 1 }

既然可以用arr.reduce计算出数组中每个元素出现的次数, 那么当然也可以由此得到下面的代码(查找数组中出现最多的元素):

const findMostElement = (arr) => {
  let res = 0;
  let count = 0;
  arr.reduce(function (obj, currentValue) {
    // console.log(obj);
    obj[currentValue] ? obj[currentValue]++ : obj[currentValue] = 1;
    if(obj[currentValue] > count) {
        count = obj[currentValue];
        res = currentValue;
    } 
    return obj;
  }, {});
  return res;
};

console.log(findMostElement([2, 2, 1, 1, 1, 2, 2]));    // 2
console.log(findMostElement([2, 2, 2, 2, 2, 2, 2]));    // 2
console.log(findMostElement([1, 2, 3, 4, 5, 6, 6]));    // 6

上述基于arr.reduce的代码的时间复杂度是O(n), 空间复杂度是O(k)(注意k为数组元素的种类)

3、其他关于arr.reduce的算法实现

当然肯定有比arr.reduce更好的写法来实现数组中出现次数最多的元素。arr.reduce更强大的一些用处在于: 数组去重、将二维数组转化为一维、将多维数组转化为一维等。

数组去重

let arr = [1,2,3,4,4,1]
let newArr = arr.reduce((pre,cur)=>{
    if(!pre.includes(cur)){
      return pre.concat(cur)
    }else{
      return pre
    }
},[])

console.log(newArr);// [1, 2, 3, 4]

将二维数组转化为一维

const arr = [
  [0, 1],
  [2, 3],
  [4, 5],
];
const newArr = function (arr) {
  return arr.reduce((pre, cur) => pre.concat(cur), []);
};

console.log(newArr(arr)); //[0,1,2,3,4,5]

将多维数组转化为一维

const arr = [
  [0, 1],
  [2, 3],
  [4, [5, 6, 7]],
];
const newArr = function (arr) {
  return arr.reduce(
    (pre, cur) => pre.concat(Array.isArray(cur) ? newArr(cur) : cur),
    []
  );
};
console.log(newArr(arr)); //[0, 1, 2, 3, 4, 5, 6, 7]

注意: 箭头函数里面当只有一条语句且没有大括号的时候可以省略return