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

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

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

и получите

[2, 3]
вопрос задан 11.12.2009
Peter
79534 репутация

36 ответов


  • 756 рейтинг

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

    array1.filter(value => -1 !== array2.indexOf(value));
    
    ответ дан Anon., с репутацией 42363, 11.12.2009
  • 152 рейтинг

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

    /* 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;
    }
    
    ответ дан atk, с репутацией 8142, 11.12.2009
  • 37 рейтинг

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

    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));
    }
    

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

    ответ дан nbarbosa, с репутацией 550, 5.05.2016
  • 19 рейтинг

    Использование Подчеркивание. JS

    _.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]
    
    ответ дан Sai Ram, с репутацией 1433, 29.09.2016
  • 12 рейтинг

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

    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;
    }
    
    ответ дан Steven Huwig, с репутацией 11996, 11.12.2009
  • 10 рейтинг

    с использованием jQuery :

    var a = [1,2,3];
    var b = [2,3,4,5];
    var c = $(b).not($(b).not(a));
    alert(c);
    
    ответ дан Gowsikan, с репутацией 2201, 25.12.2013
  • 10 рейтинг

    Мой вклад в терминах 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("
    " + JSON.stringify(arr.intersect(...arrs)) + "
    ");
    ответ дан Redu, с репутацией 11724, 15.05.2016
  • 8 рейтинг

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

    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 . Это примерно в три раза быстрее в использовании. население

    ответ дан xn., с репутацией 12273, 19.07.2012
  • 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"]; 
    
    ответ дан Tim Down, с репутацией 242875, 11.12.2009
  • 7 рейтинг

    Это довольно коротко, используя ES2015 и наборы. Принимает подобные массиву значения, такие как 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, с репутацией 458, 12.05.2017
  • 7 рейтинг
    1. Сортировать
    2. проверять по одному из индекса 0, создавать новый массив из этого.

    Нечто подобное, Не проверено хорошо, хотя.

    function intersection(x,y){
     x.sort();y.sort();
     var i=j=0;ret=[];
     while(i

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

    ответ дан YOU, с репутацией 81157, 11.12.2009
  • 7 рейтинг
    // 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 / массив-пересечение-сравнение для сравнения производительности.

    function intersect_for(a, b) {
      const result = [];
      const alen = a.length;
      const blen = b.length;
      for (let i = 0; i < alen; ++i) {
        const ai = a[i];
        for (let j = 0; j < blen; ++j) {
          if (ai === b[j]) {
            result.push(ai);
            break;
          }
        }
      } 
      return result;
    }
    
    function intersect_filter_indexOf(a, b) {
      return a.filter(el => b.indexOf(el) !== -1);
    }
    
    function intersect_filter_in(a, b) {
      const map = b.reduce((map, el) => {map[el] = true; return map}, {});
      return a.filter(el => el in map);
    }
    
    function intersect_for_in(a, b) {
      const result = [];
      const map = {};
      for (let i = 0, length = b.length; i < length; ++i) {
        map[b[i]] = true;
      }
      for (let i = 0, length = a.length; i < length; ++i) {
        if (a[i] in map) result.push(a[i]);
      }
      return result;
    }
    
    function intersect_filter_includes(a, b) {
      return a.filter(el => b.includes(el));
    }
    
    function intersect_filter_has_this(a, b) {
      return a.filter(Set.prototype.has, new Set(b));
    }
    
    function intersect_filter_has_arrow(a, b) {
      const set = new Set(b);
      return a.filter(el => set.has(el));
    }
    
    function intersect_for_has(a, b) {
      const result = [];
      const set = new Set(b);
      for (let i = 0, length = a.length; i < length; ++i) {
        if (set.has(a[i])) result.push(a[i]);
      }
      return result;
    }

    Результаты в 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, с репутацией 11278, 6.05.2017
  • 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 () ), но кажется довольно хорошим балансом. Он находится на очень простой стороне , обеспечивая при этом хорошую производительность и не требует предварительно отсортированных входов.

    ответ дан David, с репутацией 445, 26.11.2015
  • 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, с репутацией 1697, 16.07.2015
  • 4 рейтинг
    function intersection(A,B){
    var result = new Array();
    for (i=0; i
    ответ дан Gabe, с репутацией 1939, 19.09.2012
  • 4 рейтинг

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

    // 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, с репутацией 2228, 4.03.2015
  • 3 рейтинг

    "indexOf" для IE 9. 0, хром, firefox, опера,

        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]
    
    ответ дан Martin Roberto Mondragon Sotel, с репутацией 31, 28.10.2014
  • 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, с репутацией 15881, 18.05.2013
  • 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, с репутацией 220, 21.03.2017
  • 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))
    ответ дан Vlad Bezden, с репутацией 24947, 3.10.2016
  • 2 рейтинг

    Это, наверное, самый простой, кроме list1. фильтр (n = & gt; list2. включает в себя

    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
    ответ дан Chris Lwin, с репутацией 21, 3.02.2018
  • 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 с

    Если вы хотите вычислить пересечение произвольного числа Array с, просто составьте 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) );
    ответ дан ftor, с репутацией 6291, 11.10.2016
  • 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, с репутацией 21017, 2.02.2017
  • 1 рейтинг
    var listA = [1,2,3,4,5,6,7];
    var listB = [2,4,6,8];
    
    var result = listA.filter(itemA=> {
        return listB.some(itemB => itemB === itemA);
    });
    
    ответ дан jcmordan, с репутацией 696, 24.01.2017
  • 1 рейтинг

    Здесь подчеркивания. 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. орг / документы / подчеркивания. html # section-62

    ответ дан Dorian, с репутацией 12163, 30.12.2014
  • 1 рейтинг
    function getIntersection(arr1, arr2){
        var result = [];
        arr1.forEach(function(elem){
            arr2.forEach(function(elem2){
                if(elem === elem2){
                    result.push(elem);
                }
            });
        });
        return result;
    }
    
    getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ]
    
    ответ дан bekzat, с репутацией 21, 20.10.2017
  • 0 рейтинг

    Надеюсь, что это помогает для всех версий.

    function diffArray(arr1, arr2) {
      var newArr = [];
    
      var large = arr1.length>=arr2.length?arr1:arr2;
      var small = JSON.stringify(large) == JSON.stringify(arr1)?arr2:arr1;
      for(var i=0;i
    ответ дан Shubham Pandey, с репутацией 1, 29.01.2017
  • 0 рейтинг

    Если ваши массивы отсортированы, это должно выполняться в O (n), где n - min (a. длина, б. длина)

    function intersect_1d( a, b ){
        var out=[], ai=0, bi=0, acurr, bcurr, last=Number.MIN_SAFE_INTEGER;
        while( ( acurr=a[ai] )!==undefined && ( bcurr=b[bi] )!==undefined ){
            if( acurr < bcurr){
                if( last===acurr ){
                    out.push( acurr );
                }
                last=acurr;
                ai++;
            }
            else if( acurr > bcurr){
                if( last===bcurr ){
                    out.push( bcurr );
                }
                last=bcurr;
                bi++;
            }
            else {
                out.push( acurr );
                last=acurr;
                ai++;
                bi++;
            }
        }
        return out;
    }
    
    ответ дан Dave Swanson, с репутацией 11, 14.08.2018
  • 0 рейтинг

    Вот очень наивная реализация, которую я использую. Это неразрушающий и также гарантирует, что не будет дублировать записи.

    Array.prototype.contains = function(elem) {
        return(this.indexOf(elem) > -1);
    };
    
    Array.prototype.intersect = function( array ) {
        // this is naive--could use some optimization
        var result = [];
        for ( var i = 0; i < this.length; i++ ) {
            if ( array.contains(this[i]) && !result.contains(this[i]) )
                result.push( this[i] );
        }
        return result;
    }
    
    ответ дан devios1, с репутацией 18623, 16.12.2011
  • 0 рейтинг

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

    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, с репутацией 340, 9.03.2018
  • 0 рейтинг

    Следующий код также удаляет дубликаты:

           function intersect(x, y) {
                if (y.length > x.length) temp = y, y = x, x= temp;  
                return x.filter(function (e, i, c) {  
                      return c.indexOf(e) === i;
                     });
           }
    
    ответ дан Enayat Rajabi, с репутацией 813, 1.12.2017
  • 0 рейтинг

    пересечение N массивов в coffeescript

    getIntersection: (arrays) ->
        if not arrays.length
            return []
        a1 = arrays[0]
        for a2 in arrays.slice(1)
            a = (val for val in a1 when val in a2)
            a1 = a
        return a1.unique()
    
    ответ дан user1205224, с репутацией 1, 18.04.2013
  • 0 рейтинг

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

    function arrayIntersect(arrayOfArrays)
    {        
        var arrayCopy = arrayOfArrays.slice(),
            baseArray = arrayCopy.pop();
    
        return baseArray.filter(function(item) {
            return arrayCopy.every(function(itemList) {
                return itemList.indexOf(item) !== -1;
            });
        });
    }
    
    ответ дан Dag Sondre Hansen, с репутацией 1704, 26.01.2017
  • 0 рейтинг

    Я расширил ответ tarulen для работы с любым количеством массивов. Он также должен работать с нецелыми значениями.

    function intersect() { 
        const last = arguments.length - 1;
        var seen={};
        var result=[];
        for (var i = 0; i < last; i++)   {
            for (var j = 0; j < arguments[i].length; j++)  {
                if (seen[arguments[i][j]])  {
                    seen[arguments[i][j]] += 1;
                }
                else if (!i)    {
                    seen[arguments[i][j]] = 1;
                }
            }
        }
        for (var i = 0; i < arguments[last].length; i++) {
            if ( seen[arguments[last][i]] === last)
                result.push(arguments[last][i]);
            }
        return result;
    }
    
    ответ дан gabe appleton, с репутацией 61, 19.09.2016
  • -1 рейтинг

    не об эффективности, но легко следовать, вот пример объединений и пересечений множеств, он обрабатывает массивы множеств и наборы множеств.

    http: // jsfiddle. net / zhulien / NF68T /

    // process array [element, element...], if allow abort ignore the result
    function processArray(arr_a, cb_a, blnAllowAbort_a)
    {
        var arrResult = [];
        var blnAborted = false;
        var intI = 0;
    
        while ((intI < arr_a.length) && (blnAborted === false))
        {
            if (blnAllowAbort_a)
            {
                blnAborted = cb_a(arr_a[intI]);
            }
            else
            {
                arrResult[intI] = cb_a(arr_a[intI]);
            }
            intI++;
        }
    
        return arrResult;
    }
    
    // process array of operations [operation,arguments...]
    function processOperations(arrOperations_a)
    {
        var arrResult = [];
        var fnOperationE;
    
        for(var intI = 0, intR = 0; intI < arrOperations_a.length; intI+=2, intR++) 
        {
            var fnOperation = arrOperations_a[intI+0];
            var fnArgs = arrOperations_a[intI+1];
            if (fnArgs === undefined)
            {
                arrResult[intR] = fnOperation();
            }
            else
            {
                arrResult[intR] = fnOperation(fnArgs);
            }
        }
    
        return arrResult;
    }
    
    // return whether an element exists in an array
    function find(arr_a, varElement_a)
    {
        var blnResult = false;
    
        processArray(arr_a, function(varToMatch_a)
        {
            var blnAbort = false;
    
            if (varToMatch_a === varElement_a)
            {
                blnResult = true;
                blnAbort = true;
            }
    
            return blnAbort;
        }, true);
    
        return blnResult;
    }
    
    // return the union of all sets
    function union(arr_a)
    {
        var arrResult = [];
        var intI = 0;
    
        processArray(arr_a, function(arrSet_a)
        {
            processArray(arrSet_a, function(varElement_a)
            {
                // if the element doesn't exist in our result
                if (find(arrResult, varElement_a) === false)
                {
                    // add it
                    arrResult[intI] = varElement_a;
                    intI++;
                }
            });
        });
    
        return arrResult;
    }
    
    // return the intersection of all sets
    function intersection(arr_a)
    {
        var arrResult = [];
        var intI = 0;
    
        // for each set
        processArray(arr_a, function(arrSet_a)
        {
            // every number is a candidate
            processArray(arrSet_a, function(varCandidate_a)
            {
                var blnCandidate = true;
    
                // for each set
                processArray(arr_a, function(arrSet_a)
                {
                    // check that the candidate exists
                    var blnFoundPart = find(arrSet_a, varCandidate_a);
    
                    // if the candidate does not exist
                    if (blnFoundPart === false)
                    {
                        // no longer a candidate
                        blnCandidate = false;
                    }
                });
    
                if (blnCandidate)
                {
                    // if the candidate doesn't exist in our result
                    if (find(arrResult, varCandidate_a) === false)
                    {
                        // add it
                        arrResult[intI] = varCandidate_a;
                        intI++;
                    }
                }
            });
        });
    
        return arrResult;
    }
    
    var strOutput = ''
    
    var arrSet1 = [1,2,3];
    var arrSet2 = [2,5,6];
    var arrSet3 = [7,8,9,2];
    
    // return the union of the sets
    strOutput = union([arrSet1, arrSet2, arrSet3]);
    alert(strOutput);
    
    // return the intersection of 3 sets
    strOutput = intersection([arrSet1, arrSet2, arrSet3]);
    alert(strOutput);
    
    // of 3 sets of sets, which set is the intersecting set
    strOutput = processOperations([intersection,[[arrSet1, arrSet2], [arrSet2], [arrSet2, arrSet3]]]);
    alert(strOutput);
    
    ответ дан user3206335, с репутацией 17, 3.04.2014
  • -4 рейтинг

    «filter» и «indexOf» не поддерживаются в массиве в IE. Как насчет этого:

    var array1 = [1, 2, 3];
    var array2 = [2, 3, 4, 5];
    
    var intersection = [];
    for (i in array1) {
        for (j in array2) {
            if (array1[i] == array2[j]) intersection.push(array1[i]);
        }
    }
    
    ответ дан jpsimons, с репутацией 18827, 11.12.2009