的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

如果你想要一個線性複雜性解決方案，你必須權衡一些空間複雜性，以便能夠通過該陣列執行單個線性搜索。你可以做的就是將您的匹配陣列爲一組，減少O(ids.length)的ID存在查找到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));

Answer 2

假設

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 3

通過使用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的陣列。