取出现次数，怎么计算这个速度快呢？

Question

let arr = ['841', '458', '232', '101', '676', ...] // 500个成员的数组，内容都是随机三位数字

// 想写这样的一个函数，指定数量，指定位置，指定字符，
// 计算以上数组，在指定数量的成员里，指定字符在指定位置的出现次数

function calcNum(数量, 位置, 字符){
    ...
}

// 前4个成员里，第二个位置是'3'的，有几个
calcNum(4, 2, '3') -> 1

// 前3个成员里，第三个位置是'1'的，有几个
calcNum(3, 3, '1') -> 1

// 前5个成员里，第三个位置是'1'的，有几个
calcNum(5, 3, '1') -> 2

这样单个的计算，速度还行，但是这样就很慢了...

for (i=1; i<=500; i++){
    calcNum(i, 3, '1')
}

有大神能计算得快点吗？

Answer 1

解决方案是先把数据处理成更易读取的对象，避免重复计算

let arr = ['841', '458', '232', '101', '676'];

let data = arr.reduce((d, str, index) => {
  str.split('').forEach((v, i) => {
    i += 1;
    if (!d[i]) d[i] = {};
    if (!d[i][v]) d[i][v] = [];
    d[i][v].push(index);
  });
  return d;
}, {});

function calcNum(start, i, v) {
  const ary = data[i] && data[i][v] ? data[i][v] : [];
  if (ary.length) {
    const index = ary.findIndex(_i => _i >= start);
    return ary.length - (index > -1 ? index : 0);
  }
  return 0;
}

Answer 2

你能先说清楚你到底在求什么吗？

你这个 for 里面的计算结果是累加还是干嘛？

如果是 ：

let count = 0
for (i=1; i<=500; i++){
    count += calcNum(i, 3, '1')
}
// count

那么等价于

* pos: 位置, target: 字符
count = arr.reduce((p, c) => p = p * 2 + (c.split("")[pos - 1] === target ? 1 : 0), 0)

---

如果是：

for (i=1; i<=500; i++){
    let count = calcNum(i, 3, '1')
    // 仅在循环内使用 count
}

那么如评论所说可以用缓存：

let cache = 0
for (i=0; i<500; i++){
    let count = cache + (arr[i].split("")[pos - 1] === target ? 1 : 0)
    // 仅在循环内使用 count
    cache = count
}

Answer 3

只能遍历 时间复杂度 o(mn) 前m个成员中的出现次数 n是整个数组的大小
还有一个方法就是按照 fn(n) = fn(n-1)+x 将fn(n-1)的结果存储起来，用空间复杂度换时间复杂度
选择哪种看场景，刷算法的话 不用浪费时间在这种简单的算法上面。