JavaScript - 在 O(n) 中通过原始数组的内容过滤对象数组

Question

我有以下对象数组:

[{
  itemType: 'bottle',
  itemId: '111'
}, {
  itemType: 'bottle',
  itemId: '222'
}, {
  itemType: 'bottle',
  itemId: '333'
}]

我正在尝试通过如下所示的简单数组对其进行过滤(O(n) 的时间复杂度):

[ '111', '333' ]

所以最终的对象数组如下所示:

[{
  itemType: 'bottle',
  itemId: '222'
}]

我想使用 underscoreJS 但没有内置函数可以简单地完成此操作。还有其他选择吗？

Answer 1

如果您想要一个线性复杂度的解决方案，您必须权衡一些空间复杂度，以便能够在数组中执行单个线性搜索。你可以做的是将你的匹配数组转换成一个集合，减少 id 存在查找从 O(ids.length) 到 O(1) 从而减少你的总数从O(arr.length*ids.length)到O(arr.length) + O(ids.length)的复杂度:

如果您不能权衡任何空间，您的总复杂度将是二次方的:O(arr.length * ids.length)。

ES6 解决方案O(arr.length) + O(ids.length):

const arr = [{itemType: 'bottle', itemId: '111'},{itemType: 'bottle', itemId: '222'},{itemType: 'bottle', itemId: '333'}];
const ids = ['111', '333'];

function filter(arr, ids) {
  const s = new Set(ids); // O(ids.length) to build the set and use O(ids.length) space
  return arr.filter(item => s.has(item.itemId)); // O(arr.length) to filter the array
}

console.log(filter(arr, ids));

ES5 解决方案O(arr.length) + O(ids.length):

var arr = [{itemType: 'bottle', itemId: '111'},{itemType: 'bottle', itemId: '222'},{itemType: 'bottle', itemId: '333'}];
var ids = ['111', '333'];

function filter(arr, ids) {
  // O(ids.length) to build the set and use O(ids.length) space
  var s = ids.reduce(function(s, id) {
    s[id] = true;
    return s;
  }, Object.create(null));

  // O(arr.length) to filter the array
  return arr.filter(function(item) {
    return s[item.itemId];
  });
}

console.log(filter(arr, ids));