2 つの 2D リスト アルゴリズムの重複をチェックしていますか?

php エディター Baicao は、Java アルゴリズムに関する素晴らしい Q&A を提供しました: 2 つの 2 次元リスト内の重複要素をチェックするにはどうすればよいですか?これは、多くの Java プログラマーが日常の開発でよく遭遇する問題の 1 つです。この記事の議論と分析を通じて、読者はさまざまなソリューションと最適化戦略について学び、Java プログラミングにおける同様の問題に対処するための方法とテクニックをより深く理解し、習得することができます。

質問内容

2 つの list> (a と b とします) が与えられました。

返される値:map、list>>

• a と b の項目が a1、a2、a3、...、および b1、b2、b3...
であるとします。
• b1要素とa1要素(list)で重複する文字列を持つ項目のみを選択します
• 結果に key = b1、value = a1 と入力します。

＃＃＃例えば）＃＃＃ リーリー

実際には、a と b のリストの長さは少なくとも 100,000 を超えます。 list.contains を使用してこのアプローチを試しましたが、最悪の場合の時間計算量は o(n^3) でした。

これが私のコードです。このアルゴリズムの時間計算量を o(n^2) 以下に削減したいと考えています。

define a and b as follows:
a = [a, b, c], [d, e, f], [a, d, f]
b = [a, d], [a], [c], [x]

it returns : 
key        value 
[a,d]    | [a,b,c],[d,e,f],[a,d,f] 
[a]      | [a,b,c],[a,d,f] 
[c]      | [a,b,c] 
[x]      | empty list

回避策

これを

o(n^2)

未満に減らす方法があるかどうかはわかりませんが、# に減らすには##o( n^2) では、hashmap を通じて list.contains o(n)<code> .get を削減できます。つまり o(1) 時間の複雑さ。 contains

をチェックするのではなく、リスト

a 内の要素のインデックスを探すことをお勧めします。b 要素はそのインデックスを取得し、 a 対応リスト。 まず、a

の要素をキーとして、値をインデックスとして含む

map を構築します。 リーリー これは ainset

の出力です。これで、それが属する要素のインデックス リストが得られます。

リーリー 次に、b

の要素リストのインデックスを結合して、

a の対応する要素を取得します。 たとえば、[a, d]

の場合、組み合わせセット

[0, 1, 2] があります。これはコードです リーリー

以上が2 つの 2D リスト アルゴリズムの重複をチェックしていますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。