如何正确地在数组中计算出现次数？

Question

我有一个深度数组（数组的数组）。 我试图编写一个不使用任何额外方法和JS设计（如闭包）的良好函数。

以下是一个可行的解决方案（但由于全局变量而不好）。

  var counter = 0;

  function findArray(array, item) {
      for (var i = 0; i < array.length; i++) {
          if (array[i] == item) {
              counter++;
          } else if (array[i].constructor === Array) {
              findArray(array[i], item);
          }
      }
      return counter;
  }

这是一种无法工作的解决方案，试图避免全局计数器变量。

  function findArray(array, item, counter) {
    for (var i = 0; i < array.length; i++) {
        if (array[i] == item) {
            ++counter;
        }
        if (array[i].constructor === Array) {
            findArray(array[i], item, counter);
        }
    }
    return counter;
}

我希望您能避免使用计数器输入参数，因为参数应该只是输入，并且输出变量不应该在函数参数内。此外，我想避免使用内置的方法，例如slice等。

注意：不应考虑算法的最佳性能。

有没有办法使计数器位于函数内部？

函数调用如下：

findArray([1,[1,2,3],1,[5,9,1],6],  1,0);

在这个例子中，应该输出数字4（整数1是要在数组中搜索的数字）。

- EugenSunic

Answer 1

这是一个关于递归的用例。（也是关于Array.isArray的，该函数在ES5中被添加。）findArray可以通过调用自身来查找数组中的出现情况：

function findArray(array, item) {
    var counter = 0;
    for (var i = 0; i < array.length; i++) {
        var entry = array[i];
        if (entry == item){
            counter++;
        } else if (Array.isArray(entry)) {
            // Add in the count of occurrences in the array, and any arrays in it
            counter += findArray(entry, item);
        }
    }
    return counter;
}

这也是使用 Array#reduce 方法的一种情况:

function findArray(array, item) {
    return array.reduce(function(counter, entry) {
        if (entry == item) {
            ++counter;
        }
        if (Array.isArray(entry)) {
            counter += findArray(entry, item);
        }
        return counter;
    }, 0);
}

Array#reduce 方法会在数组中的每个元素上调用一次回调函数，每次调用时将当前元素和累加器作为参数传入。累加器的初始值可以作为第二个参数提供（某些情况下是可选的，但在这里不是）；回调函数返回的更新后的累加器将成为最终返回的 reduce 的值。

- T.J. Crowder

---

你能想到一种如何创建TCO的方法吗？ - Max Koretskyi

@Maximus：我不明白为什么“reduce”版本不符合TCO（潜伏者：尾调用优化）的要求。但你必须有荒谬地嵌套数组才会有影响。 - T.J. Crowder

@T.J.Crowder，我认为不是这样的，因为您在函数调用之后执行了其他操作。 - Max Koretskyi

@Maximus：不，在“reduce”版本中，函数调用在尾部位置。但我不知道闭包如何影响任何事情，我还没有研究过TCO要求。 - T.J. Crowder

Answer 2

您的想法是正确的。您可以将第一个递归函数修改为：

function findArray(array, item) {
  var occurrences = 0;

  for (var i = 0; i < array.length; i++) {
    if (array[i] == item) {
      // Found an occurrence.
      occurrences++;
    } else if (array[i].constructor === Array) {
      // Add all occurrences in the sub-array i
      occurrences += findArray(array[i], item);
    }
  }

  return occurrences;
}


console.log(findArray([1, [1, 2, 3], 1, [5, 9, 1], 6], 1, 0));

使用reduce调用可以缩短它，其思想与上述相同：

function findArray(array, item) {
  return array.reduce((occur, e) =>
    occur + ((Array.isArray(e)) ? findArray(e, item) : (e == item)), 0);
}

console.log(findArray([1, [1, 2, 3], 1, [5, 9, 1], 6], 1, 0));

- John Bupit

Answer 3

另一种，也许更易理解的解决方案：

function sumValues(array) {
    let counter = 0;
    for (let item of array) {
      if (Array.isArray(item)) {
        counter += sumValues(item);
      }
      else {
        counter += item;
      }
    }
    return counter;
  }

- EugenSunic

Answer 4

我相信这是迄今为止最好的解决方案：

const countOccurs = (arr, val) =>
  arr.reduce((prev, curr) => {
    if (Array.isArray(curr)) {
       return prev + countOccurs(curr, val);
    }

    if (curr !== val) {
      return prev;
    }

    return prev + curr;
  }, 0);

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

我们在这里所做的是，使用Array.prototype.reduce遍历提供的数组，并检查值的任何出现情况。如果数组的实际值（curr）是一个数组，则函数调用自身以进行检查并将结果添加到计数器（prev）中。

- primq

Answer 5

可用的JSBin：http://jsbin.com/sayimecezo/edit?html,js,console,output

您可以简单地展开嵌套数组并对其进行过滤。（这里仅为方便而覆盖原型）。

Array.prototype.countDeep = function (n) {
  return [].concat.apply([], this).filter(function (f) {
    return f === n;
  }).length;
}

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

将值填充到记忆化的变量中非常简单（尽管不必要）;

Array.prototype.countDeep = function (n, seed) {
  return (seed || 0) + [].concat.apply([], this).filter(function (f) {
    return f === n;
  }).length;
}

console.log(([1,[1,2,3],1,[5,9,1],6]).countDeep(1, 200));
//prints 204

- BluePill