Как избежать вложенного цикла в реальном тесте кодирования Javascript

Question

Между двумя входными массивами найдите один и тот же массив или массивы и верните их.

Я просто мог бы придумать решение для вложенных циклов.

const compareArrs = (arr1, arr2) => {
  const rtnArr = []
  for (let ar1 of arr1){
    for (let ar2 of arr2){
      if (JSON.stringify(ar1) === JSON.stringify(ar2)){
        rtnArr.push(ar1)
      }
    }
  }
  return rtnArr
}

// compare [1, 2] [3, 4] with [1, 2]
console.log(compareArrs([[1, 2], [3, 4]], [[1, 2]]))

[[1, 2]] должны быть возвращены.

Answer 1

Отобразите каждый подмассив одного аргумента и поместите его в набор. С другим аргументом, итерируйте его, проводя по порядку строку, и найдите элемент, для которого строковый массив уже находится в наборе, для общей сложности O(N):

const compareArrs = (arr1, arr2) => {
  const arr1StringifiedSet = new Set(arr1.map(JSON.stringify));
  return arr2.find(
    subarr2 => arr1StringifiedSet.has(JSON.stringify(subarr2))
  );
};

console.log(compareArrs([[1, 2], [3, 4]], [[1, 2]]));

(Для сравнения, вложенный цикл имеет сложность O(N^2))

Как отмечается в комментариях, если вам действительно нужно все соответствующие массивы, а не только первый, то используйте .filter вместо .find:

const compareArrs = (arr1, arr2) => {
  const arr1StringifiedSet = new Set(arr1.map(JSON.stringify));
  return arr2.filter(
    subarr2 => arr1StringifiedSet.has(JSON.stringify(subarr2))
  );
};

console.log(compareArrs([[1, 2], [3, 4]], [[1, 2]]));

Answer 2

Вы можете использовать Array.prototype.reduce () в сочетании с Array.prototype.find () и Array.prototype.push ()

const compareArrs = (arr1, arr2) => arr1.reduce((a, c) => {
  const found = arr2.find(arr => JSON.stringify(arr) === JSON.stringify(c))
  if (found.length) a.push(found)
  return a
}, [])

// compare [1, 2] [3, 4] with [1, 2]
console.log(compareArrs([[1, 2]], [[1, 2], [3, 4]]))

Answer 3

Вы можете имитировать набор массивов с вложенными картами, где [1, 2] становится записью в корневой карте, где ключ равен 1, а значением является другая карта с ключом 2, например:

const present = Symbol('present');

class ArraySet {
    constructor() {
        this._root = new Map();
    }

    add(array) {
        let node = this._root;

        for (const item of array) {
            if (node.has(item)) {
                node = node.get(item);
            } else {
                node.set(item, node = new Map());
            }
        }

        node[present] = true;
    }

    has(array) {
        let node = this._root;

        for (const item of array) {
            node = node.get(item);

            if (node === undefined) {
                return false;
            }
        }

        return !!node[present];
    }
}

тогда:

const compareArrs = (arr1, arr2) => {
    const set = new ArraySet();
    arr1.forEach(set.add, set);
    return arr2.filter(set.has, set);
};

const present = Symbol('present');

class ArraySet {
    constructor() {
        this._root = new Map();
    }

    add(array) {
        let node = this._root;

        for (const item of array) {
            if (node.has(item)) {
                node = node.get(item);
            } else {
                node.set(item, node = new Map());
            }
        }

        node[present] = true;
    }

    has(array) {
        let node = this._root;

        for (const item of array) {
            node = node.get(item);

            if (node === undefined) {
                return false;
            }
        }

        return !!node[present];
    }
}

const compareArrs = (arr1, arr2) => {
    const set = new ArraySet();
    arr1.forEach(set.add, set);
    return arr2.filter(set.has, set);
};

console.log(compareArrs([[1, 2], [3, 4]], [[1, 2]]));

Это занимает время, пропорциональное arr1.concat(arr2).flat().length. Другой подход, который работает до тех пор, пока вы можете создать подходящую функцию сравнения для массивов, как этот лексикографический, когда обычные операторы JavaScript дают полный порядок:

const lexCompare = (a, b) => {
    const len = Math.min(a.length, b.length);

    for (let i = 0; i < len; i++) {
        if (a[i] < b[i]) return -1;
        if (a[i] > b[i]) return 1;
    }

    return a.length - b.length;
};

и входные массивы не содержат дубликатов - сначала сортировать комбинацию обоих массивов:

const sorted = arr1.concat(arr2).sort(lexCompare);

затем ищите дубликаты, созданные слиянием рядом друг с другом:

return sorted.filter((item, i) => {
    if (i === 0) return false;

    const prev = sorted[i - 1];
    return prev.length === item.length && prev.every((x, i) => x === item[i]);
});

за время O ((| arr1 | + | arr2 |) log (| arr1 | + | arr2 |) l) где l - максимальная длина массива. Вы можете уменьшить этот (| arr1 | + | arr2 |) log (| arr1 | + | arr2 |) до | arr1 | log | arr1 | + | arr2 | log | arr2 | но это может закончиться медленнее.