So, as an input I have two arrays, A and B. Let's suppose that these are the values inside the two:
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and B = [1, 3, 5, 7, 9]
After the deletion the array A should be [2, 4, 6, 8, 10].
I have written (Javascript) this functioning algorithm to solve this problem:
for (var i=0; i < A.length; i ) {
for (var j=0; j < B.length; j ) {
if(B[j] == A[i])
A.splice(i, 1) // Removes 1 element of the array starting from position i
}
}
I would like to know, is it possible to solve this problem without using a double loop?
CodePudding user response:
What about this:
let A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ;
const B = [1, 3, 5, 7, 9];
A = A.filter(num => !B.includes(num));
CodePudding user response:
Yes it is. You could use a Set
. In terms of Set operations you are computing the difference A \ B
.
Using a set which is optimized for lookups in O(1)
time will speed up the computing the difference siginificantly from O(n²)
when using includes()
or double for
loop to O(n)
.
const A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const B = [1, 3, 5, 7, 9]
const setB = new Set(B);
const difference = A.filter(x => !setB.has(x));
console.log(difference);
CodePudding user response:
Maybe that ?
const
A = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
, B = [ 1, 3, 5, 7, 9 ]
;
for (let i = A.length, j= B.length -1 ; i-- ; )
{
if (A[i]===B[j]) { A.splice(i,1); j-- }
}
document.write( JSON.stringify(A) )