JavaScript

Question

我有以下对象数组：

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

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

[ '111', '333' ]

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

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

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

Answer 1

假设

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

和

var b = [ '111', '333' ]

所以使用下划线方法可以简单地完成：

_.filter(a, function(ele) {
    return !_.contains(b, ele.itemId)
})

Answer 2

通过对黑名单使用 Set，我们可以删除重复项并节省查找时间。

const blacklist = new Set(['111', '333']);
const items = [
    {
        itemType : 'bottle',
        itemId   : '111'
    },
    {
        itemType : 'bottle',
        itemId   : '222'
    },
    {
        itemType : 'bottle',
        itemId   : '333'
    }
];

const filtered = items.filter((item) => {
    return !blacklist.has(item.itemId);
});

在上面的代码中，filtered是items个对象的数组，itemId没有出现在blacklist上。

Answer 3

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

如果您不能权衡 space，您的总复杂度将是二次方的：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));

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

JavaScript - filter array of objects by content of primitive array in O(n)

arrays

time-complexity

underscore.js