【前端问题精选】取出现次数,怎么计算这个速度快呢?

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')

}

有大神能计算得快点吗?

回答:

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

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;

}

回答:

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

你这个 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

}

回答:

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

以上是 【前端问题精选】取出现次数,怎么计算这个速度快呢? 的全部内容, 来源链接: www.h5w3.com/134348.html

回到顶部