Как може да се оптимизира алгоритъмът за пресичане?

Оптимизацията на алгоритъма за пресичане (intersection) на два масива или списъка зависи от първоначалната реализация и изискванията.

Типични подходи:

1. Използване на множество (Set)

Ако първоначалният алгоритъм е вложени цикли (O(n*m)), може значително да се ускори, като се преобразува един от списъците в множество за бързо търсене (O(1) средно):

function intersection(arr1, arr2) {
  const set2 = new Set(arr2);
  return arr1.filter(item => set2.has(item));
}

2. Сортиране и метод с два указателя

Ако данните са сортирани или могат да бъдат сортирани, може да преминавате двата масива с два указателя, което дава O(n log n + m log m) заради сортирането, но O(n + m) след това:

function intersectionSorted(arr1, arr2) {
  arr1.sort();
  arr2.sort();
  let i = 0, j = 0;
  const result = [];
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] === arr2[j]) {
      result.push(arr1[i]);
      i++; j++;
    } else if (arr1[i] < arr2[j]) {
      i++;
    } else {
      j++;
    }
  }
  return result;
}

3. Вземане предвид на спецификата на данните

Ако данните са много големи, може да се използват по-сложни структури или паралелна обработка.

Общо взето, използването на множество е най-простият и ефективен начин за повечето случаи.