返回数组A中除在B中出现p次的元素的序列

Question

我想写一个函数，它接收两个序列:a和B，并返回序列C，该序列C应该包含a中的所有元素(按顺序)，除了在B中出现p次的元素。

例如序列

=(2、3、9、2、5、1、3、7、10]

B =(2, 1, 3, 4, 3, 10日,6日6日1、7、10、10、10]

应该返回C =[2、9、2、5、7、10]

当p = 2

我是这样写的:

function cSequence(a, b, p) {
const times = {};
b.forEach((item) => {
if (times[item]) {
times[item] += 1;
} else {
times[item] = 1;
}
});
const pTimes = b.filter((item) => (times[item] == p ? true : false));
return a.filter((item) => !pTimes.includes(item));
}

但是就时间复杂度而言，有没有更好的方法来做到这一点呢?

我的解应该表示为O(3n)还是O(n)?

Answer 1

在时间复杂度方面是否有更好的方法?

不要在filter回调中使用includes()!它的时间复杂度是二次的。您已经有了一个按项目查找的映射，只需直接使用它来实现线性解决方案!去除中间的pTimes:

function cSequence(a, b, p) {
const times = {};
for (const item of b) {
if (item in times) {
times[item] += 1;
} else {
times[item] = 1;
}
}
return a.filter(item => times[item] != p);
}

我的溶液应该表示为O(3n)还是O(n)?

这是一样的。常数因子在朗道表示法中被忽略。

Answer 2

您可以使用Array.prototype.reduce()创建bHash对象，该对象包含所有出现的总数

然后是array。prototype。filter() arrayA不包括在数组Bp中重复出现的元素

代码:

const A = [2,3,9,2,5,1,3,7,10]
const B = [2,1,3,4,3,10,6,6,1,7,10,10,10]
const p = 2
const cSequence = (arrA, arrB, p) => {
const bHash = arrB.reduce((a, c) => (a[c] ??= 0, a[c]++, a), {})
return arrA.filter(n => bHash[n] !== p)
}
console.log(cSequence(A, B, p))