两个包含对象的数组的差异和交集

Question

我有两个数组list1和list2，它们包含一些具有属性的对象；其中userId是ID或唯一属性：

list1 = [
    { userId: 1234, userName: 'XYZ'  }, 
    { userId: 1235, userName: 'ABC'  }, 
    { userId: 1236, userName: 'IJKL' },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
]

list2 = [
    { userId: 1235, userName: 'ABC'  },  
    { userId: 1236, userName: 'IJKL' },
    { userId: 1252, userName: 'AAAA' }
]

我希望您能提供一个简单的方法来执行以下三个操作：

1. list1 operation list2 应该返回元素的交集：

   [
       { userId: 1235, userName: 'ABC'  },
       { userId: 1236, userName: 'IJKL' }
   ]
   

2. list1操作list2应返回list1中所有不在list2中出现的元素列表:

[
    { userId: 1234, userName: 'XYZ'  },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
]

3. list2 operation list1 应该返回所有在list2中出现但不在list1中出现的元素列表：

[
    { userId: 1252, userName: 'AAAA' }
]

- Shashi

---

你的标题说“差异”，但你的问题提到了“交集”。它是哪一个？你能举个例子说明你希望输出什么吗？ - Mr. Llama

https://lodash.com/docs#intersection - Mike Robinson

@MikeRobinson 使用 lodash 对我来说不起作用，因为它没有正确比较对象。 - lumos42

Answer 1

您可以定义三个函数inBoth，inFirstOnly和inSecondOnly，它们都以两个列表作为参数，并从函数名中可以理解返回一个列表。主要逻辑可以放在一个通用的函数operation中，所有三个函数都依赖于它。

这里有几个实现operation的选择，可以在下面的片段中找到：

• 普通的JavaScript for循环
• 使用filter和some数组方法的箭头函数
• 优化的查找与Set

普通的for循环

// Generic helper function that can be used for the three operations:        
function operation(list1, list2, isUnion) {
    var result = [];
    
    for (var i = 0; i < list1.length; i++) {
        var item1 = list1[i],
            found = false;
        for (var j = 0; j < list2.length && !found; j++) {
            found = item1.userId === list2[j].userId;
        }
        if (found === !!isUnion) { // isUnion is coerced to boolean
            result.push(item1);
        }
    }
    return result;
}

// Following functions are to be used:
function inBoth(list1, list2) {
    return operation(list1, list2, true);
}

function inFirstOnly(list1, list2) {
    return operation(list1, list2);
}

function inSecondOnly(list1, list2) {
    return inFirstOnly(list2, list1);
}

// Sample data
var list1 = [
    { userId: 1234, userName: 'XYZ'  }, 
    { userId: 1235, userName: 'ABC'  }, 
    { userId: 1236, userName: 'IJKL' },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
];
var list2 = [
    { userId: 1235, userName: 'ABC'  },  
    { userId: 1236, userName: 'IJKL' },
    { userId: 1252, userName: 'AAAA' }
];
  
console.log('inBoth:', inBoth(list1, list2)); 
console.log('inFirstOnly:', inFirstOnly(list1, list2)); 
console.log('inSecondOnly:', inSecondOnly(list1, list2)); 

使用filter和some数组方法的箭头函数

这个例子使用了一些ES5和ES6特性：

// Generic helper function that can be used for the three operations:        
const operation = (list1, list2, isUnion = false) =>
    list1.filter( a => isUnion === list2.some( b => a.userId === b.userId ) );

// Following functions are to be used:
const inBoth = (list1, list2) => operation(list1, list2, true),
      inFirstOnly = operation,
      inSecondOnly = (list1, list2) => inFirstOnly(list2, list1);

// Sample data
const list1 = [
    { userId: 1234, userName: 'XYZ'  }, 
    { userId: 1235, userName: 'ABC'  }, 
    { userId: 1236, userName: 'IJKL' },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
];
const list2 = [
    { userId: 1235, userName: 'ABC'  },  
    { userId: 1236, userName: 'IJKL' },
    { userId: 1252, userName: 'AAAA' }
];
  
console.log('inBoth:', inBoth(list1, list2)); 
console.log('inFirstOnly:', inFirstOnly(list1, list2)); 
console.log('inSecondOnly:', inSecondOnly(list1, list2));

优化查找

由于嵌套循环的存在，上述解决方案的时间复杂度为O(n²)。因此，对于大型数组，最好基于用户ID创建一个（临时的）哈希表。可以通过在函数参数中提供一个Set（ES6）来实现即时生成哈希表。该函数可以生成过滤回调函数，并使用has在常数时间内执行查找：

// Generic helper function that can be used for the three operations:        
const operation = (list1, list2, isUnion = false) =>
    list1.filter(
        (set => a => isUnion === set.has(a.userId))(new Set(list2.map(b => b.userId)))
    );

// Following functions are to be used:
const inBoth = (list1, list2) => operation(list1, list2, true),
      inFirstOnly = operation,
      inSecondOnly = (list1, list2) => inFirstOnly(list2, list1);

// Sample data
const list1 = [
    { userId: 1234, userName: 'XYZ'  }, 
    { userId: 1235, userName: 'ABC'  }, 
    { userId: 1236, userName: 'IJKL' },
    { userId: 1237, userName: 'WXYZ' }, 
    { userId: 1238, userName: 'LMNO' }
];
const list2 = [
    { userId: 1235, userName: 'ABC'  },  
    { userId: 1236, userName: 'IJKL' },
    { userId: 1252, userName: 'AAAA' }
];
  
console.log('inBoth:', inBoth(list1, list2)); 
console.log('inFirstOnly:', inFirstOnly(list1, list2)); 
console.log('inSecondOnly:', inSecondOnly(list1, list2));

- trincot

---

"优化查找"部分有太多的移动部件。干得好，谢谢。 - monsto

Answer 2

简短回答：

list1.filter(a => list2.some(b => a.userId === b.userId));  
list1.filter(a => !list2.some(b => a.userId === b.userId));  
list2.filter(a => !list1.some(b => a.userId === b.userId));  

详细回答：
以上代码将通过userId值检查对象，
如果您需要使用复杂的比较规则，可以定义自定义比较器：

comparator = function (a, b) {
    return a.userId === b.userId && a.userName === b.userName
};  
list1.filter(a => list2.some(b => comparator(a, b)));
list1.filter(a => !list2.some(b => comparator(a, b)));
list2.filter(a => !list1.some(b => comparator(a, b)));

还有一种方法可以通过引用比较对象。
警告！两个具有相同值的对象将被视为不同：

o1 = {"userId":1};
o2 = {"userId":2};
o1_copy = {"userId":1};
o1_ref = o1;
[o1].filter(a => [o2].includes(a)).length; // 0
[o1].filter(a => [o1_copy].includes(a)).length; // 0
[o1].filter(a => [o1_ref].includes(a)).length; // 1

- Trizalio

---

太棒了！干净利落！ - ProblemsEverywhere

Answer 3

只需使用JS的filter和some数组方法即可实现。

let arr1 = list1.filter(e => {
   return !list2.some(item => item.userId === e.userId);
});

这将返回在list1中存在但不在list2中的项。如果你想寻找两个列表中的共同项，只需这样做。

let arr1 = list1.filter(e => {
   return list2.some(item => item.userId === e.userId); // take the ! out and you're done
});

- Koushik Das

Answer 4

使用lodash的_.isEqual方法。具体如下：

list1.reduce(function(prev, curr){
  !list2.some(function(obj){
    return _.isEqual(obj, curr)
  }) ? prev.push(curr): false;
  return prev
}, []);

上面的代码相当于 SQL 里的 A LEFT OUTER JOIN B，你可以移动这段代码来得到你想要的结果！

- Bwaxxlo

Answer 5

function intersect(first, second) {
    return intersectInternal(first, second, function(e){ return e });
}

function unintersect(first, second){
    return intersectInternal(first, second, function(e){ return !e });  
}

function intersectInternal(first, second, filter) {
    var map = {};

    first.forEach(function(user) { map[user.userId] = user; });

    return second.filter(function(user){ return filter(map[user.userId]); })
}

- Sagi

Answer 6

这是对我有效的解决方案。

 var intersect = function (arr1, arr2) {
            var intersect = [];
            _.each(arr1, function (a) {
                _.each(arr2, function (b) {
                    if (compare(a, b))
                        intersect.push(a);
                });
            });

            return intersect;
        };

 var unintersect = function (arr1, arr2) {
            var unintersect = [];
            _.each(arr1, function (a) {
                var found = false;
                _.each(arr2, function (b) {
                    if (compare(a, b)) {
                        found = true;    
                    }
                });

                if (!found) {
                    unintersect.push(a);
                }
            });

            return unintersect;
        };

        function compare(a, b) {
            if (a.userId === b.userId)
                return true;
            else return false;
        }

- Shashi

Answer 7

这是一个使用underscore/lodash的函数式编程解决方案来回答你的第一个问题（交集）。

list1 = [ {userId:1234,userName:'XYZ'}, 
          {userId:1235,userName:'ABC'}, 
          {userId:1236,userName:'IJKL'},
          {userId:1237,userName:'WXYZ'}, 
          {userId:1238,userName:'LMNO'}
        ];

list2 = [ {userId:1235,userName:'ABC'},  
          {userId:1236,userName:'IJKL'},
          {userId:1252,userName:'AAAA'}
        ];

_.reduce(list1, function (memo, item) {
        var same = _.findWhere(list2, item);
        if (same && _.keys(same).length === _.keys(item).length) {
            memo.push(item);
        }
        return memo
    }, []);

我会让你改进这个来回答其他的问题 ;-)

- laruiss

---

在真正的函数式编程风格中，不会有 push（它会改变数组）。 - trincot

Answer 8

Typescript和@trincot答案的更通用版本

type Primative = string | number | boolean
type GetId<T> = (item: T) => Primative

const operation = <T, U, B extends boolean>(
  list1: T[],
  list2: U[],
  isUnion: B,
  getList1Id: GetId<T>,
  getList2Id: GetId<U>,
): T[] =>
  list1.filter(
    (a) => isUnion === list2.some((b) => getList1Id(a) === getList2Id(b)),
  )

export const inBoth = <T, U>(
  list1: T[],
  list2: U[],
  getList1Id: GetId<T>,
  getList2Id: GetId<U>,
): T[] => operation(list1, list2, true, getList1Id, getList2Id)

export const inFirstOnly = <T, U>(
  list1: T[],
  list2: U[],
  getList1Id: GetId<T>,
  getList2Id: GetId<U>,
): T[] => operation(list1, list2, false, getList1Id, getList2Id)

export const inSecondOnly = <T, U>(
  list1: T[],
  list2: U[],
  getList1Id: GetId<T>,
  getList2Id: GetId<U>,
): U[] => operation(list2, list1, false, getList2Id, getList1Id)

- BryceLarkin