Сократите время для сравнения двух массивов.Сложность времени

Question

Мне нужна помощь специалиста / совет, как лучше подойти к этой проблеме. У меня есть два массива, и мне нужно сравнить эти два массива. Скажем, у меня есть 2 массива для сравнения, array1 & array2, и мне нужно проверить, существуют ли значения в массиве 1 в массиве 2, в PHP я могу использовать функцию «array_diff», которая работает каждый раз, но я не хочу использовать array_diff, потому что интервьюер говорит, что это не так просто, и он хочет, чтобы я сделал это по-другому.

По умолчанию я думаю, что нужно перебрать массив1, и для каждого значения массива1 снова сравнить этот массив2, две итерации, это будет (n * n) сложность по времени, см. Мой код ниже.

Как мне улучшить этот алгоритм / код. Моя цель - проверить, есть ли значение одного массива в другом. Как мне улучшить этот код, чтобы сравнение двух массивов не заняло так много времени.

Это касается вопросов интервью, а также моего ежедневного кодирования приложений, которые я делаю каждый день

const array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"];
const array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"];

for (let index1 of array1){
  for (let index2 of array2){
    if (index1 === index2){
      console.log("Exists.", "index 1 value: " + index1, "Index 2 value: " + index2)
    }
  } 
}

Мне нужно улучшить время. Еще одна сложность времени, которая не является квадратичной.

Answer 1

Вы можете взять Set и проверить каждый элемент другого массива.

var array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"],
    array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"],
    set1 = new Set(array1);

array2.forEach(v => {
    if (set1.has(v)) console.log(v);
});

Если вы хотите получить только общие элементы, вы можете отфильтровать массив.

var array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"],
    array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"],
    common = array2.filter(Set.prototype.has, new Set(array1));

console.log(...common);

Answer 2

Я изменю его с массива на Map, а затем выполню поиск

const array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"];
const array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"];

let arr1Map = new Map([...array1.map((v,i)=>[v,i])])

array2.forEach(val=> arr1Map.has(val) && console.log(val))

Answer 3

При добавлении каждого значения в массив1 добавьте его также в объект / кэш:

var cache = {};
...
...
for (index in array2) {
    cahce.array1_value = array1_value + '##' + array2[index] + '%%' + index;
}

Затем при проверке выполните:

 for (let index1 of array1){
    var s = split(cache[array[index1]], '%%');
    if (cache[array1[index1]] === s[0]){
      console.log("Exists." + index1 + '/' + s[1]);
    }
  }

Это не проверено, иэто только для того, чтобы дать представление.

Он должен иметь сложность O (n).

Это также зависит от того, какой массив вы заполняете первым

Но это не сработаеткогда оба массива создаются одновременно (вы не упомянули, как создаются массивы).

Требуется дополнительное время, когда создаются массивы, но никто не сказал, что это следует учитывать.:) Кроме того, это решение подходит для реальных приложений, но не для интервью.

Answer 4

Вы можете использовать хэш-таблицу для хранения первых элементов массива, а затем запрашивать вторые элементы массива.Это работает в O (n) следующим образом:

1. Установка элементов в HashSet займет O (n).

2. Запрос элемента в HashSet будет O (1) согласно амортизированному анализу.

Answer 5

Вы можете использовать include и indexOf:

var array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"],
    array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"];

    array1.forEach( (value,index1) => {
      if(array2.includes(value)){
         var index2 = array2.indexOf(value);
         console.log(value + " found index1:" + index1 + ", index2:" + index2);
      }
});

Answer 6

Это довольно медленно

https://jsperf.com/array-indexof-vs-set-has

const array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"];
const array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"];
console.log(
  array1.filter((arr1) => array2.indexOf(arr1) != -1)
);