javascript - 2 つの配列の和集合から交差部分を除いたものを見つけるための優れたアルゴリズムは何ですか?
过去多啦不再A梦
过去多啦不再A梦 2017-06-26 10:51:43
0
6
1524
リーリー

重複要素を削除した後、2 つの配列のマージされた配列を検索します (両側の重複要素を削除することを指します。たとえば、3 が繰り返された場合、結果に 3 が含まれることはありません。これは配列の重複排除とは異なります)。配列の和集合です。交差部分を減算する部分ですが、この部分に数学的な名前があるかどうかはわかりません。時間の複雑さが低いアルゴリズムをお探しですか?

过去多啦不再A梦
过去多啦不再A梦

全員に返信(6)
大家讲道理

set をインデックスとして使用し、短い O(n) を走査します

リーリー
いいねを押す +0
为情所困

2 つのセットの重複しない部分を見つけるには、まず 2 つのセットの和集合を見つけてから、共通の要素を削除します。
A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }

プログラムのアイデアを使用した実装は次のとおりです。
2 つの配列をマージし、フィルター メソッドを使用して配列 a と b の交差要素をフィルターで除外します。 a が b に含まれておらず、b が a に含まれていない a.concat(b) 内の要素をフィルターで除外します。主に配列に要素が含まれているかどうかの判定を行うもので、実装方法としては Array.prototype.indexOf、Set の has メソッド、Array.prototype.includes の 3 つがあります。

NaNを考慮せずにES5のindexOfメソッドを利用した実装方法:

リーリー

ES6 の新しい Set コレクション メソッドを使用し、filter メソッドと組み合わせて、結合された配列をフィルター処理します。

リーリー

ES7 の新しい Array.prototype.includes 配列メソッドを使用して、配列に指定された要素が含まれているかどうかを返し、それを filter メソッドと組み合わせて、マージされた配列をフィルター処理します。

リーリー
いいねを押す +0
伊谢尔伦

この結果は対称差分と呼ばれ、セットまたはマルチセットで定義されます

複雑さ...平均的 O(n)

いいねを押す +0
仅有的幸福

リーリー

----------私は間違った質問を読みました、答えは間違っています、上記は重複を削除しただけです、以下を参照してください---------------

----------基本的な for ループをたどるだけで完了できます------

リーリー
いいねを押す +0
黄舟

最初の方法、

リーリー

2 番目のタイプ、concat と filter、原則はマージしてから重複を削除することです

リーリー
いいねを押す +0
女神的闺蜜爱上我

オブジェクトのプロパティを使用して実装する

リーリー

スクリーンショット

いいねを押す +0
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート