2016-09-28 8 views
3

I持つオブジェクトの以下の配列:はJavaScript - O(n)のプリミティブ配列の内容によって、オブジェクトのフィルタアレイ

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

私はフィルタリングしようとしている(Oの時間計算量を(n))を、それを次のような単純な配列によって:私は0を使用して考え

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

[ '111', '333' ] 

だから、オブジェクトの最後の配列は次のようになりますしかし、簡単な方法でこれを実現する組み込み関数はありません。その他のオプションは?

+0

番目の反復処理eソース配列を削除するには、IDのセットを使用します。これには、削除するデータ構造が異なる必要がありますが、1回の繰り返しでO(n)のままです。 –

答えて

2

線形複雑さのソリューションを使用するには、配列を1回の線形検索で実行できるように、空間の複雑さをトレードオフする必要があります。あなたにできることはO(ids.length)からO(1)にIDの存在のルックアップを減らすため、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));

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) 
}) 
+1

これはO(n)ではありません。 – iblamefish

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); 
}); 

filtereditemIdblacklistに表示されないitemsオブジェクトの配列です。

関連する問題