Простейший код для пересечения массива в JavaScript

611

Какой самый простой, свободный от библиотек код для реализации пересечений массивов в javascript? Я хочу написать

intersection([1,2,3], [2,3,4,5])

и получить

[2, 3]
Питер
источник
16
Вы хотите простой или быстрый?
SLaks
11
Приоритет прост, но он не может быть настолько умопомрачительным, что это будет свинья производительности :)
Питер
4
Я сделал тестовую страницу JsFiddle Banchmark для всех методов, включая функцию пересечения _underscore . (чем выше, тем лучше) ! введите описание изображения здесь До сих пор intersect_safe давал лучшие результаты . ВЫ и подчеркиваете худшее.
neoswf
Добавление breakк Simple js loopsувеличивает число операций в секунду до ~ 10M
Ричард
19
Если вы его пропустили : самый простой ответ - не принятый, а приведенный внизу: stackoverflow.com/questions/1885557/…
redben

Ответы:

1081

Используйте комбинацию Array.prototype.filterи Array.prototype.indexOf:

array1.filter(value => -1 !== array2.indexOf(value))

Или, как предложил Вругтехагель в комментариях, вы можете использовать более свежую версиюArray.prototype.includes для еще более простого кода:

array1.filter(value => array2.includes(value))

Для старых браузеров:

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});
Anon.
источник
9
Что вы можете решить, добавив версию библиотеки на прототип массива.
Анон.
12
Да, но это стоило упомянуть.
Тим Даун
18
Лучший ответ здесь, как для простоты, так и для работы с нечисловыми числами
Muhd
41
intersection([1,2,1,1,3], [1])возвращается [1, 1, 1]. Разве это не должно вернуться просто [1]?
edjroot
21
Вместо этого array2.indexOf(n) != -1можно также написать array2.includes(n)для еще более простого кода.
vrugtehagel
157

Деструктивный кажется самым простым, особенно если мы можем предположить, что вход отсортирован:

/* destructively finds the intersection of 
 * two arrays in a simple fashion.  
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *  State of input arrays is undefined when
 *  the function returns.  They should be 
 *  (prolly) be dumped.
 *
 *  Should have O(n) operations, where n is 
 *    n = MIN(a.length, b.length)
 */
function intersection_destructive(a, b)
{
  var result = [];
  while( a.length > 0 && b.length > 0 )
  {  
     if      (a[0] < b[0] ){ a.shift(); }
     else if (a[0] > b[0] ){ b.shift(); }
     else /* they're equal */
     {
       result.push(a.shift());
       b.shift();
     }
  }

  return result;
}

Неразрушающий должен быть более сложным, так как мы должны отслеживать показатели:

/* finds the intersection of 
 * two arrays in a simple fashion.  
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *
 *  Should have O(n) operations, where n is 
 *    n = MIN(a.length(), b.length())
 */
function intersect_safe(a, b)
{
  var ai=0, bi=0;
  var result = [];

  while( ai < a.length && bi < b.length )
  {
     if      (a[ai] < b[bi] ){ ai++; }
     else if (a[ai] > b[bi] ){ bi++; }
     else /* they're equal */
     {
       result.push(a[ai]);
       ai++;
       bi++;
     }
  }

  return result;
}
атк
источник
14
Существует множество ошибок intersect_safe: lengthэто свойство в массивах, а не метод. Есть незадействованная переменная iв result.push(a[i]);. Наконец, это просто не работает в общем случае: два объекта, где ни один не больше другого согласно >оператору, не обязательно равны. intersect_safe( [ {} ], [ {} ] )например, даст (после исправления ранее упомянутых ошибок) массив с одним элементом, что явно неверно.
Тим Даун
1
@Tim Down: исправлены синтаксические ошибки, которые вы указали. Правильно или неверно считать что-либо ни gerater, ни меньше, чтобы быть равными, зависит от требований. Я ничего не заметил в исходном вопросе о том, что содержимое должно содержать массивы. Теперь, вы бы правильно сказали, что неожиданный ввод должен обрабатываться, но если в спецификации уже указывалось, что ввод должен быть массивом чисел (как я и предполагал), тогда код будет в порядке.
ака
1
@atk: Я понимаю вашу точку зрения, поскольку в качестве примера в вопросе используются массивы, которые содержат только цифры.
Тим Даун
4
Вы также можете использовать .slice(0)для создания клона массива intersect_safe, а не отслеживания индексов.
johnluetke
1
@thesmart: вы правы, есть определенно более эффективные способы сделать это. Код выше должен был быть простым, а не быстрым :)
atk
59

Если ваша среда поддерживает набор ECMAScript 6 , один простой и предположительно эффективный (см. Ссылку на спецификацию) способ:

function intersect(a, b) {
  var setA = new Set(a);
  var setB = new Set(b);
  var intersection = new Set([...setA].filter(x => setB.has(x)));
  return Array.from(intersection);
}

Короче, но менее читабельно (также без создания дополнительного пересечения Set):

function intersect(a, b) {
      return [...new Set(a)].filter(x => new Set(b).has(x));
}

Избежать новое Setот bкаждого времени:

function intersect(a, b) {
      var setB = new Set(b);
      return [...new Set(a)].filter(x => setB.has(x));
}

Обратите внимание, что при использовании наборов вы получите только различные значения, поэтому new Set[1,2,3,3].sizeоцените их 3.

nbarbosa
источник
1
что это за [...setA]синтаксис? Какой-то особый вид работы с JavaScript?
jxramos
1
@jxramos - это синтаксис Spread, и в данном случае он просто используется для создания массива из элементов в наборе. «Array.from (setA)» также будет работать в этом случае, но так как вопрос, заданный для «простейшего», я попытался сделать его чище, чтобы читать в этой строке. В этом отношении я думаю, что код может быть проще, поэтому я обновлю фрагмент.
Нбарбоса
@nbarbosa Мне интересно: почему вы "клонировали" массив a? #filter не уничтожает исходный массив, верно? Это создает новый массив?
17
@bplittle Я только что создал массив из набора, чтобы удалить дубликаты, в противном случае использование массива напрямую приведет к возврату дубликатов. Например, если бы я использовал массив напрямую, пересечение ([1,2,2,4], [2,3]) привело бы к [2, 2].
nbarbosa
2
Разве эта x => new Set(b).has(x)функция стрелки не превращается bв набор каждый раз, когда она выполняется? Вы, вероятно, должны сохранить этот набор в переменной.
Аран-Фей
39

Использование Underscore.js или lodash.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]
Сай Рам
источник
20
Оп спросил "без библиотеки".
LinuxDisciple
@LinuxDisciple Моя ошибка, что я пропустил это. Спасибо за заметки
Сай Рам
33
В любом случае, это лучший список Google для этого поиска, поэтому полезно иметь ответ из библиотеки. Спасибо.
webnoob
Я тоже рад, что это было опубликовано. Впервые я почувствовал необходимость в underscore.js. Обычно карты JavaScript и конвейеры сокращения делают работу элегантно, но не в этот раз.
Шридхар Сарнобат
Я <3 Подчеркиваю, и я <3 Джереми Ашкенас (его создатель), но даже в этом случае я НАСТОЯТЕЛЬНО рекомендую проверить Lodash вместо этого. Это в основном улучшенная версия Underscore (изначально она была форком), единственным недостатком которой является супероптимизированный (и, следовательно, почти нечитаемый) исходный код. Люди Underscore даже подумали полностью избавиться от Underscore (и просто сказать людям использовать Lodash), но люди, которым небезразлична читаемость исходного кода, утверждали, что сохраняют его (на самом деле я был на этой стороне, но с тех пор я перешел на Lodash). @see github.com/jashkenas/underscore/issues/2182
machineghost
14

Мой вклад в терминах ES6. В общем случае он находит пересечение массива с неопределенным числом массивов, предоставляемых в качестве аргументов.

Array.prototype.intersect = function(...a) {
  return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));
}
var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]],
     arr = [0,1,2,3,4,5,6,7,8,9];

document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");

Redu
источник
этот код выглядит великолепно, но я не понимаю его полностью. Можно это объяснить, пожалуйста?
обычно
1
@novembersky Он собирает все предметные массивы в массив, как [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8],[4,5,6,7],[4,6]]и затем применяется .reduce(). Первая [0,1,2,3,4,5,6,7,8,9].filter( e => [0,2,4,6,8].includes(e)операция выполняется , и результат становится новым pи cстановится [4,5,6,7]в следующем повороте и продолжает так далее вверх до тех пор, пока больше не cосталось.
Ред.
1
Это дорогое решение, если вы работаете с большими наборами данных.
Madbreaks
1
Не модифицируйте prototypeизлишне.
fregante
14

// Return elements of array a that are also in b in linear time:
function intersect(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

// Example:
console.log(intersect([1,2,3], [2,3,4,5]));

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

Альтернативы и сравнение производительности:

Посмотрите следующий фрагмент для альтернативных реализаций и проверьте https://jsperf.com/array-intersection-comparison для сравнения производительности.

Результаты в Firefox 53:

  • Операций в секунду на больших массивах (10 000 элементов):

    filter + has (this)               523 (this answer)
    for + has                         482
    for-loop + in                     279
    filter + in                       242
    for-loops                          24
    filter + includes                  14
    filter + indexOf                   10
  • Операций в секунду на небольших массивах (100 элементов):

    for-loop + in                 384,426
    filter + in                   192,066
    for-loops                     159,137
    filter + includes             104,068
    filter + indexOf               71,598
    filter + has (this)            43,531 (this answer)
    filter + has (arrow function)  35,588
le_m
источник
2
intersect([1,2,2,3], [2,3,4,5])возвращается [2, 2, 3].
SeregPie
1
@SeregPie Точно. Согласно комментарию «Вернуть элементы массива a, которые также находятся в b»
le_m
Качественный ответ, однако использование множеств в корне меняет результаты, поскольку в операционном вопросе задан вопрос только о пересечениях массивов и не упоминается / не указывается, как обрабатывать дубликаты. Стесняется этого, этот ответ может привести к неожиданным результатам при наличии дубликатов.
Madbreaks
1
Понравилось, но вы добавили ненужную функцию с «filter + includes». попробуй a.filter(b.includes). Он должен работать значительно быстрее (так же, как обновление вашей функции).
19
11

Как насчет использования ассоциативных массивов?

function intersect(a, b) {
    var d1 = {};
    var d2 = {};
    var results = [];
    for (var i = 0; i < a.length; i++) {
        d1[a[i]] = true;
    }
    for (var j = 0; j < b.length; j++) {
        d2[b[j]] = true;
    }
    for (var k in d1) {
        if (d2[k]) 
            results.push(k);
    }
    return results;
}

редактировать:

// new version
function intersect(a, b) {
    var d = {};
    var results = [];
    for (var i = 0; i < b.length; i++) {
        d[b[i]] = true;
    }
    for (var j = 0; j < a.length; j++) {
        if (d[a[j]]) 
            results.push(a[j]);
    }
    return results;
}
Стивен Хьюиг
источник
1
Это имеет шанс только в том случае, если ваши массивы содержат только строки или числа, и если ни один из сценариев на вашей странице не был испорчен Object.prototype.
Тим Даун
2
В примере OP использовались числа, и если сценарий перепутался с Object.prototype, сценарий должен быть переписан или удален.
Стивен Хувиг
Вам не нужны оба (d1) и (d2). Создайте (d2), затем выполните цикл (a) вместо цикла (d1).
СтэнлиХ,
Должно быть d[b[i]] = true;вместо d[b[j]] = true;( iнет j). Но редактирование требует 6 символов.
Изаки
@ Ижаки спасибо, исправлено. (Добавлен // комментарий, чтобы обойти минимальные требования редактирования.)
Стивен Хьюиг
8
  1. Сортировать
  2. проверяйте по одному из индекса 0, создавайте новый массив из этого.

Как-то так, не проверено хорошо, хотя.

function intersection(x,y){
 x.sort();y.sort();
 var i=j=0;ret=[];
 while(i<x.length && j<y.length){
  if(x[i]<y[j])i++;
  else if(y[j]<x[i])j++;
  else {
   ret.push(x[i]);
   i++,j++;
  }
 }
 return ret;
}

alert(intersection([1,2,3], [2,3,4,5]));

PS: алгоритм предназначен только для чисел и нормальных строк, пересечение массивов произвольных объектов может не работать.

ВЫ
источник
3
Сортировка не обязательно поможет для массивов произвольных объектов
Тим Даун
Если массив не отсортирован, необходимо выполнить цикл около 1 000 000 раз, когда вы пересекаете массив 1000 длин и массив 1000 длин
ВЫ
Я думаю, что вы упустили мою мысль, что произвольные объекты в JavaScript не имеют естественного порядка сортировки, то есть сортировка массива произвольных объектов не приведет к группированию одинаковых объектов. Бесполезно иметь эффективный алгоритм, который не работает.
Тим Даун
Ах, извините, я пропустил "произвольные объекты", да, вы правы. эти объекты не могут отсортировать его, и алгоритм может не работать с ними.
ВЫ
8

Производительность реализации @ atk для отсортированных массивов примитивов можно улучшить, используя .pop, а не .shift.

function intersect(array1, array2) {
   var result = [];
   // Don't destroy the original arrays
   var a = array1.slice(0);
   var b = array2.slice(0);
   var aLast = a.length - 1;
   var bLast = b.length - 1;
   while (aLast >= 0 && bLast >= 0) {
      if (a[aLast] > b[bLast] ) {
         a.pop();
         aLast--;
      } else if (a[aLast] < b[bLast] ){
         b.pop();
         bLast--;
      } else /* they're equal */ {
         result.push(a.pop());
         b.pop();
         aLast--;
         bLast--;
      }
   }
   return result;
}

Я создал тест, используя jsPerf: http://bit.ly/P9FrZK . Это примерно в три раза быстрее .pop.

хп.
источник
1
Как примечание для других - это будет работать только для чисел, а не для строк.
Изаки
Обратите внимание , что если заменить a[aLast] > b[bLast]с a[aLast].localeCompare(b[bLast]) > 0(и то же самое с else ifниже) , то это будет работать на струнах.
Андрей
1
Разница в скорости зависит от размера массивов, потому что .popэто O (1) и .shift()O (n)
Esailija
8

Используя jQuery :

var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
Gowsikan
источник
8
Это также можно записать как c = $(b).filter(a);, но я бы не рекомендовал полагаться на jQuery для такого рода манипуляций с массивами, поскольку в документации упоминается только то, что это работает для элементов.
Страйнер,
1
Это не отвечает на вопрос
опа
7

Для массивов, содержащих только строки или числа, вы можете сделать что-то с сортировкой, как в некоторых других ответах. Для общего случая массивов произвольных объектов, я не думаю, что вы можете избежать этого. Следующее даст вам пересечение любого количества массивов, предоставленных в качестве параметров для arrayIntersection:

var arrayContains = Array.prototype.indexOf ?
    function(arr, val) {
        return arr.indexOf(val) > -1;
    } :
    function(arr, val) {
        var i = arr.length;
        while (i--) {
            if (arr[i] === val) {
                return true;
            }
        }
        return false;
    };

function arrayIntersection() {
    var val, arrayCount, firstArray, i, j, intersection = [], missing;
    var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array

    // Search for common values
    firstArray = arrays.pop();
    if (firstArray) {
        j = firstArray.length;
        arrayCount = arrays.length;
        while (j--) {
            val = firstArray[j];
            missing = false;

            // Check val is present in each remaining array 
            i = arrayCount;
            while (!missing && i--) {
                if ( !arrayContains(arrays[i], val) ) {
                    missing = true;
                }
            }
            if (!missing) {
                intersection.push(val);
            }
        }
    }
    return intersection;
}

arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"]; 
Тим Даун
источник
Это работает только в случае, когда идентичность объекта является единственной формой равенства.
Стивен Хьюиг
Ну да, но я думаю, что это кажется естественным для большинства людей. Также легко подключить альтернативную функцию для выполнения другого теста на равенство.
Тим Даун
Я думаю, что вы случайно создаете глобальную переменную firstArr в вашем примере.
Джейсон Джексон,
@JasonJackson: Ты прав, спасибо. Ясно передумал, вызывать ли переменную firstArrили firstArrayне обновил все ссылки. Исправлена.
Тим Даун
7

Это довольно коротко, используя ES2015 и Sets. Принимает подобные массиву значения, такие как String, и удаляет дубликаты.

let intersection = function(a, b) {
  a = new Set(a), b = new Set(b);
  return [...a].filter(v => b.has(v));
};

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

console.log(intersection('ccaabbab', 'addb').join(''));

SeregPie
источник
Преобразование из Set в массив с помощью [... a] удалит дублирующиеся элементы, хорошая идея, спасибо
V-SHY
1
Это решение было предоставлено дважды до вашего.
Madbreaks
7

Вы могли бы использовать в Setкачестве thisArgиз Array#filterи взять в Set#hasкачестве обратного вызова.

function intersection(a, b) {
    return a.filter(Set.prototype.has, new Set(b));
}

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

Нина Шольц
источник
Я не знаю, почему это не набрало больше голосов. Это явно лучший ответ.
Пол Руни
5

Небольшая настройка на самое маленькое здесь (решение filter / indexOf ), а именно создание индекса значений в одном из массивов с использованием объекта JavaScript, уменьшит его с O (N * M) до «вероятно» линейного времени. источник1 источник2

function intersect(a, b) {
  var aa = {};
  a.forEach(function(v) { aa[v]=1; });
  return b.filter(function(v) { return v in aa; });
}

Это не самое простое решение (это больше кода, чем filter + indexOf ), и при этом оно не является самым быстрым (вероятно, медленнее на постоянный коэффициент, чем intersect_safe () ), но кажется довольно хорошим балансом. Он очень прост и обеспечивает хорошую производительность и не требует предварительно отсортированных входных данных.

Дэвид
источник
5

Еще один индексированный подход, способный обрабатывать любое количество массивов одновременно:

// Calculate intersection of multiple array or object values.
function intersect (arrList) {
    var arrLength = Object.keys(arrList).length;
        // (Also accepts regular objects as input)
    var index = {};
    for (var i in arrList) {
        for (var j in arrList[i]) {
            var v = arrList[i][j];
            if (index[v] === undefined) index[v] = 0;
            index[v]++;
        };
    };
    var retv = [];
    for (var i in index) {
        if (index[i] == arrLength) retv.push(i);
    };
    return retv;
};

Он работает только для значений, которые могут быть оценены как строки, и вы должны передать их как массив, например:

intersect ([arr1, arr2, arr3...]);

... но он прозрачно принимает объекты как параметр или как любой из элементов, которые должны быть пересечены (всегда возвращает массив общих значений). Примеры:

intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]

РЕДАКТИРОВАТЬ: я только заметил, что это, в некотором смысле, немного глючит.

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

Но если входные массивы содержат повторения, это приведет к неверным результатам. Пример (используя приведенную ниже реализацию):

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]

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

Изменить:

        if (index[v] === undefined) index[v] = 0;
        index[v]++;

по:

        if (index[v] === undefined) index[v] = {};
        index[v][i] = true; // Mark as present in i input.

...а также:

         if (index[i] == arrLength) retv.push(i);

по:

         if (Object.keys(index[i]).length == arrLength) retv.push(i);

Полный пример:

// Calculate intersection of multiple array or object values.
function intersect (arrList) {
    var arrLength = Object.keys(arrList).length;
        // (Also accepts regular objects as input)
    var index = {};
    for (var i in arrList) {
        for (var j in arrList[i]) {
            var v = arrList[i][j];
            if (index[v] === undefined) index[v] = {};
            index[v][i] = true; // Mark as present in i input.
        };
    };
    var retv = [];
    for (var i in index) {
        if (Object.keys(index[i]).length == arrLength) retv.push(i);
    };
    return retv;
};

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]
bitifet
источник
2
Это далеко лучший ответ с небольшой модификацией. После var v = строки добавить if (typeof v == 'function') continue;и пропустить добавление функций к результатам. Спасибо!
Жолти
Спасибо @Zsolti. Я не добавляю ваше предложение, потому что наличие функций (и того, как мы хотим их обрабатывать) выходит за рамки первоначального вопроса. Но посмотрите мое редактирование: если у вас могут быть повторения в ваших входных массивах, то оригинальная реализация глючит. Я исправил это в своем редактировании. ... С другой стороны, если вы точно знаете, что повторений не будет, оригинальная реализация будет немного дешевле.
битифет
... о функциях, они также могут пересекаться: если мы обнаружим их, как говорит @Zsolti (с if (typeof v == 'function'), тогда мы можем использовать его stringification ( v.toString()) в качестве ключа для индекса. Но нам нужно что-то сделать, чтобы сохранить его в целости. Самый простой способ сделать это - просто назначить исходную функцию как значение вместо простого логического истинного значения, но в этом случае следует также изменить последний деиндексат, чтобы обнаружить это условие и восстановить правильное значение (функцию).
bitifet
Как быстро это может быть с 30 массивами с 100 элементами ... как загрузка процессора?
aidonsnous
5

Вы можете использовать (для всех браузеров, кроме IE):

const intersection = array1.filter(element => array2.includes(element));

или для IE:

const intersection = array1.filter(element => array2.indexOf(element) !== -1);
jota3
источник
Было бы хорошо, если бы вы могли превратить это в функцию
avalanche1
@ avalanche1 const intersection = (a1, a2) => a1.filter (e => a2.include (e));
Jota3
4
function intersection(A,B){
var result = new Array();
for (i=0; i<A.length; i++) {
    for (j=0; j<B.length; j++) {
        if (A[i] == B[j] && $.inArray(A[i],result) == -1) {
            result.push(A[i]);
        }
    }
}
return result;
}
Гейб
источник
4

С некоторыми ограничениями на ваши данные, вы можете сделать это за линейное время!

Для натуральных чисел : используйте массив, отображающий значения в логическое значение «видел / не видел».

function intersectIntegers(array1,array2) { 
   var seen=[],
       result=[];
   for (var i = 0; i < array1.length; i++) {
     seen[array1[i]] = true;
   }
   for (var i = 0; i < array2.length; i++) {
     if ( seen[array2[i]])
        result.push(array2[i]);
   }
   return result;
}

Для объектов существует аналогичная техника : возьмите фиктивный ключ, установите его в «true» для каждого элемента в массиве array1, затем ищите этот ключ в элементах array2. Вымойтесь, когда закончите.

function intersectObjects(array1,array2) { 
   var result=[];
   var key="tmpKey_intersect"
   for (var i = 0; i < array1.length; i++) {
     array1[i][key] = true;
   }
   for (var i = 0; i < array2.length; i++) {
     if (array2[i][key])
        result.push(array2[i]);
   }
   for (var i = 0; i < array1.length; i++) {
     delete array1[i][key];
   }
   return result;
}

Конечно, вы должны быть уверены, что ключ не появлялся раньше, иначе вы уничтожите свои данные ...

tarulen
источник
Кстати, это может быть легко расширено для пересечения любого числа массивов: замените логическое значение на целые числа и увеличивайте при каждом его отображении: вы можете легко прочитать пересечение в последнем раунде.
tarulen
Интересное решение, мне это нравится. Большинство других решений O (n ^ 2), но это O (n). Я добавил целочисленный код к скрипте производительности ericP здесь jsfiddle.net/321juyLu/2 . Это пришло 3-е, мне нравится :)
rmcsharry
3

Я внесу свой вклад в то, что получилось лучше для меня:

if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {

    var r = [], o = {}, l = this.length, i, v;
    for (i = 0; i < l; i++) {
        o[this[i]] = true;
    }
    l = arr1.length;
    for (i = 0; i < l; i++) {
        v = arr1[i];
        if (v in o) {
            r.push(v);
        }
    }
    return r;
};
}
Johan
источник
3

"indexOf" для IE 9.0, Chrome, Firefox, Opera,

    function intersection(a,b){
     var rs = [], x = a.length;
     while (x--) b.indexOf(a[x])!=-1 && rs.push(a[x]);
     return rs.sort();
    }

intersection([1,2,3], [2,3,4,5]);
//Result:  [2,3]
Мартин Роберто Мондрагон Сотел
источник
2

'use strict'

// Example 1
function intersection(a1, a2) {
    return a1.filter(x => a2.indexOf(x) > -1)
}

// Example 2 (prototype function)
Array.prototype.intersection = function(arr) {
    return this.filter(x => arr.indexOf(x) > -1)
} 

const a1 = [1, 2, 3]
const a2 = [2, 3, 4, 5]

console.log(intersection(a1, a2))
console.log(a1.intersection(a2))

Влад Безден
источник
2

Функциональный подход с ES2015

Функциональный подход должен предусматривать использование только чистых функций без побочных эффектов, каждая из которых связана только с одной работой.

Эти ограничения улучшают компоновку и возможность повторного использования задействованных функций.

// small, reusable auxiliary functions

const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// run it

console.log( intersect(xs) (ys) );

Обратите внимание, что используется нативный Setтип, который имеет полезную производительность поиска.

Избегайте дубликатов

Очевидно, многократно встречающиеся элементы первого Arrayсохраняются, а второй Arrayдедуплицируется. Это может быть или не быть желаемым поведением. Если вам нужен уникальный результат, просто примените dedupeк первому аргументу:

// auxiliary functions

const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// de-duplication

const dedupe = comp(afrom) (createSet);


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// unique result

console.log( intersect(dedupe(xs)) (ys) );

Вычислить пересечение любого числа Arrayс

Если вы хотите вычислить пересечение произвольного числа Arrays, просто составьте intersectс foldl. Вот удобная функция:

// auxiliary functions

const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// intersection of an arbitrarily number of Arrays

const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];


// run

console.log( intersectn(xs, ys, zs) );


источник
Впечатляюще функционально: пришлось сделать двойной дубль, чтобы подтвердить, что это не Haskell. Единственный придира: (expr ? true : false)это избыточно. Используйте только exprесли фактические логические значения не нужны, просто истина / ложь.
jose_castro_arnaud
2

Для простоты:

// Usage
const intersection = allLists
  .reduce(intersect, allValues)
  .reduce(removeDuplicates, []);


// Implementation
const intersect = (intersection, list) =>
  intersection.filter(item =>
    list.some(x => x === item));

const removeDuplicates = (uniques, item) =>
  uniques.includes(item) ? uniques : uniques.concat(item);


// Example Data
const somePeople = [bob, doug, jill];
const otherPeople = [sarah, bob, jill];
const morePeople = [jack, jill];

const allPeople = [...somePeople, ...otherPeople, ...morePeople];
const allGroups = [somePeople, otherPeople, morePeople];

// Example Usage
const intersection = allGroups
  .reduce(intersect, allPeople)
  .reduce(removeDuplicates, []);

intersection; // [jill]

Льготы:

  • грязь просто
  • ориентированные на данные
  • работает для произвольного числа списков
  • работает для произвольной длины списков
  • работает для произвольных типов значений
  • работает для произвольного порядка сортировки
  • сохраняет форму (порядок первого появления в любом массиве)
  • выходить рано, где это возможно
  • память безопасна, если не вмешиваться в прототипы функций / массивов

Недостатки:

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

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

Norguard
источник
2

.reduceпостроить карту и .filterнайти пересечение. deleteв пределах .filterпозволяет нам рассматривать второй массив как уникальный набор.

function intersection (a, b) {
  var seen = a.reduce(function (h, k) {
    h[k] = true;
    return h;
  }, {});

  return b.filter(function (k) {
    var exists = seen[k];
    delete seen[k];
    return exists;
  });
}

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

Belden
источник
2

Это, вероятно, самый простой способ , кроме list1.filter (n => list2.include (n))

var list1 = ['bread', 'ice cream', 'cereals', 'strawberry', 'chocolate']
var list2 = ['bread', 'cherry', 'ice cream', 'oats']

function check_common(list1, list2){
	
	list3 = []
	for (let i=0; i<list1.length; i++){
		
		for (let j=0; j<list2.length; j++){	
			if (list1[i] === list2[j]){
				list3.push(list1[i]);				
			}		
		}
		
	}
	return list3
	
}

check_common(list1, list2) // ["bread", "ice cream"]

Крис Лвин
источник
это имеет O (нм) сложность времени ... это можно решить за O (n + m)
alchuang
2

Если вам нужно, чтобы он обрабатывал пересекающиеся несколько массивов:

const intersect = (a, b, ...rest) => {
  if (rest.length === 0) return [...new Set(a)].filter(x => new Set(b).has(x));
  return intersect(a, intersect(b, ...rest));
};

console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1])) // [1,2]

Belfordz
источник
Но насколько быстро это решение для 30 массивов с 100 элементами?
aidonsnous
Он использует только нативные методы Javascript, и поэтому виртуальная машина, в которой будет выполняться код, может оптимизировать его настолько, насколько это возможно. Я совершенно уверен, что не существует более быстрого решения, если вы используете его в современной версии V8 относительно возраста этого комментария.
Белфордз
2

Стиль ES6 простой способ.

const intersection = (a, b) => {
  const s = new Set(b);
  return a.filter(x => s.has(x));
};

Пример:

intersection([1, 2, 3], [4, 3, 2]); // [2, 3]
Михаил Горелышев
источник
2

Я написал функцию пересечения, которая может даже обнаружить пересечение массива объектов на основе конкретного свойства этих объектов.

Например,

if arr1 = [{id: 10}, {id: 20}]
and arr2 =  [{id: 20}, {id: 25}]

и мы хотим пересечение на основе idсвойства, то результат должен быть:

[{id: 20}]

Также, функция для того же самого (примечание: код ES6):

const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
    const [fn1, fn2] = accessors;
    const set = new Set(arr2.map(v => fn2(v)));
    return arr1.filter(value => set.has(fn1(value)));
};

и вы можете вызвать функцию как:

intersect(arr1, arr2, [elem => elem.id, elem => elem.id])

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

Мридул Мехария
источник
2

Думаю, это будет быстрее, если время O (array1 + array2) при условии, что map.has () равно ~ O (1). Пожалуйста, исправьте меня, если ошиблись.

const intersection = (a1, a2) => {
  let map = new Map();
  let result = []
  for (let i of a1) {
    if (!map.has(i)) map.set(i, true);
  }
  for (let i of a2) {
    if (map.has(i)) result.push(i)
  }
  return result;
}

ajaix
источник
1

Вот реализация underscore.js :

_.intersection = function(array) {
  if (array == null) return [];
  var result = [];
  var argsLength = arguments.length;
  for (var i = 0, length = array.length; i < length; i++) {
    var item = array[i];
    if (_.contains(result, item)) continue;
    for (var j = 1; j < argsLength; j++) {
      if (!_.contains(arguments[j], item)) break;
    }
    if (j === argsLength) result.push(item);
  }
  return result;
};

Источник: http://underscorejs.org/docs/underscore.html#section-62

Дориан
источник
Неплохая справка, если есть доступный
undesrcore