Как найти пересечение множества массивов?

Question

[Mykola Dzedzinskyi]

Всем привет!
Интересует такой вопрос : Как найти пересечение множества массивов?
Тоесть, есть некий массив массивов, типа:
[[obj1, obj2, obj3, .....],[obj4, obj2, obj5,.....],[obj3, obj5],[obj1],[obj2, obj1], ....],
нужно в результате получить массив обьектов, что являеться пересечением. Может кто писал что нибуть подобное? Конечно можно писать свой "велосипед", но мне это не срочно нужно, поэтому у кого есть идеи, буду рад вашему ответу!

Нужно написать функцию на JavaScript, мне главное производительность и красота кода! Конечно, код писать никого я не прошу, просто идеи....

Answer 1

[overmes]

function lenSort(a, b) {
    return a.length - b.length;
}

var intersec = module.exports = function(arrays) {
    arrays.sort(lenSort);

    var arraysDicts = [];
    for (var arrayIndex = 1; arrayIndex < arrays.length; arrayIndex++) {
        var dict = {};
        for (var index = 0; index < arrays[arrayIndex].length; index++) {
            dict[arrays[arrayIndex][index]] = true;
        }
        arraysDicts.push(dict);
    }

    var res = [];
    for (var index = 0; index < arrays[0].length; index++) {
        var flag = true;
        for (var arrayIndex = 0; arrayIndex < arraysDicts.length; arrayIndex++) {
            if (!(arrays[0][index] in arraysDicts[arrayIndex])) {
                flag = false;
                break;
            }
        }
        if (flag) res.push(arrays[0][index]);
    }

    return res;
};

работает за O(N+M+...), где N и M длины массивов. Быстрее мне ничего найти не удалось.

Comments

[Mykola Dzedzinskyi]

спасибо, то что нужно!

Answer 2

[Илья Милошевич]

В таких библиотеках, как underscore и lodash есть метод под названием "intersection". Можно посмотреть реализацию данного метода для каждой из этих библиотек соответственно здесь и здесь.

Answer 3

[Alex Kheben]

Массив объектов: stackoverflow.com/questions/8672383/how-to-use-und...
Массив скалярных значений: stackoverflow.com/questions/1885557/simplest-code-...