80

2 つのリスト (必ずしもソートされているとは限りません) が与えられた場合、これらのリストの集合の共通部分を見つけるための最も効率的な非再帰アルゴリズムは何ですか?
ハッシュアルゴリズムにアクセスできるとは思えません。

4

15 に答える 15

43

最初のリストのすべての要素をハッシュ セットに入れることができます。次に、2 番目のものを繰り返し、その要素ごとにハッシュをチェックして、最初のリストに存在するかどうかを確認します。もしそうなら、交差点の要素として出力します。

于 2009-01-30T21:39:46.167 に答える
26

ブルーム フィルターを確認することをお勧めします。これらは、要素がセットのメンバーであるかどうかの確率的な答えを与えるビット ベクトルです。セット交差は、単純なビットごとの AND 演算で実装できます。null 交差が多数ある場合、ブルーム フィルターを使用すると、それらをすばやく排除できます。ただし、実際の交点を計算するには、ここで説明した他のアルゴリズムのいずれかに頼る必要があります。 http://en.wikipedia.org/wiki/Bloom_filter

于 2010-05-23T16:22:00.213 に答える
10

ハッシュなしでは、2 つのオプションがあると思います。

  • 単純な方法は、各要素を他のすべての要素と比較することです。O(n^2)
  • 別の方法は、最初にリストを並べ替えてから、それらを反復処理することです: O(n lg n) * 2 + 2 * O(n)
于 2009-01-30T21:49:10.970 に答える
7

eviews 機能リストから、複雑なマージと結合をサポートしているようです (これが DB 用語のように「結合」である場合、交差を計算します)。ドキュメントを掘り下げてください:-)

さらに、eviews には独自のユーザー フォーラムがあります。そこで質問してみてはいかがでしょうか_

于 2010-05-23T16:56:30.090 に答える
6

C++ では、STL マップを使用して以下を試すことができます

vector<int> set_intersection(vector<int> s1, vector<int> s2){

    vector<int> ret;
    map<int, bool> store;
    for(int i=0; i < s1.size(); i++){

        store[s1[i]] = true;
    }
    for(int i=0; i < s2.size(); i++){

        if(store[s2[i]] == true) ret.push_back(s2[i]);

    }
    return ret;
}
于 2010-05-07T04:41:33.397 に答える
6

セット 1 で二分探索木を構築し、セット 2O(log n)を反復しBST m X O(log n)て合計を検索しますO(log n) + O(m)+O(log n) ==> O(log n)(m+1)

于 2011-04-21T02:23:55.863 に答える
3

これは、私が思いついた別の可能な解決策であり、時間の複雑さで O(nlogn) かかり、追加のストレージはありません。ここで確認できますhttps://gist.github.com/4455373

セットに繰り返しが含まれていないと仮定して、すべてのセットを 1 つにマージし、並べ替えます。次に、マージされたセットをループし、各反復で現在のインデックス i と i+n の間のサブセットを作成します。ここで、n はユニバースで使用可能なセットの数です。ループするときに探すのは、宇宙のセットの数に等しいサイズ n の繰り返しシーケンスです。

i の部分集合が n の部分集合と等しい場合、これは i の要素が n 回繰り返されることを意味し、これは集合の総数に等しい。また、どのセットにも繰り返しがないため、各セットにその値が含まれていることを意味するため、共通部分に追加します。次に、インデックスを i + それと n の間に残っているものだけシフトします。これは、これらのインデックスのいずれも繰り返しシーケンスを形成しないためです。

于 2013-01-04T19:55:31.677 に答える
2

スキップ ポインターとSSE 命令を使用すると、リスト交差の効率を向上させることができます。

于 2016-06-16T14:11:25.140 に答える
2

最初に、クイックソート O(n*log(n) を使用して両方のリストをソートします。次に、最初に最も低い値を参照してリストを比較し、共通の値を追加します。たとえば、 lua) で:

function findIntersection(l1, l2)
    i, j = 1,1
    intersect = {}

    while i < #l1 and j < #l2 do
        if l1[i] == l2[i] then
            i, j = i + 1, j + 1
            table.insert(intersect, l1[i])
        else if l1[i] > l2[j] then
            l1, l2 = l2, l1
            i, j = j, i
        else
            i = i + 1
        end
    end

    return intersect
end

これはO(max(n, m))、リストnのmサイズです。

EDIT：コメントで述べたように、クイックソートは再帰的ですが、非再帰的な 実装があるようです

于 2009-01-30T21:47:50.067 に答える
1

私は「セット」のアイデアを2番目にしています。JavaScriptでは、リスト要素を名前として使用して、最初のリストを使用してオブジェクトにデータを入力できます。次に、2番目のリストのリスト要素を使用して、それらのプロパティが存在するかどうかを確認します。

于 2009-01-31T22:55:26.467 に答える
1

独自の単純なハッシュ テーブルまたはハッシュ セットを実装してみませんか? あなたが言うようにリストが大きい場合は、 nlogn 交差を避ける価値があります。

事前にデータについて少し知っているので、適切なハッシュ関数を選択できるはずです。

于 2009-01-30T21:53:09.387 に答える
1

組み込みとしてセット(タイトルでそれらを呼び出すように)のサポートがある場合、通常、交差メソッドがあります。

とにかく、リストがソートされていれば、誰かが簡単にできると言ったように（コードは投稿しません。誰かがすでに投稿しています）。再帰が使えなくても問題ありません。クイックソートの再帰のない実装があります。

于 2009-01-30T21:54:16.107 に答える
0

Big-Oh表記の定義から：

N ≥ n 0 のときに T(N) ≤ cf(N) となるような正の定数 c および n 0 がある場合、T(N) = O(f(N))。

これは実際には、2 つのリストのサイズが比較的小さい場合、2 つの for ループごとに 100 要素未満でうまく機能することを意味します。最初のリストをループし、2 番目のリストで同様のオブジェクトを探します。私の場合、リストに 10 ～ 20 個の最大要素しかないため、問題なく動作します。ただし、良い解決策は、最初の O(n log n) を並べ替え、2 番目も O(n log n) を並べ替えてマージし、別の O(n log n) で大まかに O(3 n log n) を並べ替えることです。 2 つのリストは同じサイズです。

于 2015-10-19T10:08:28.163 に答える
0

時間: O(n) 空間: O(1)交点を特定するための解。

たとえば、指定された 2 つのノードは、終点に到達するたびにポインタを交換することで交点を検出します。動画解説はこちら。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA;
    ListNode pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

ありがとう。

編集

私の交差点の解釈は、交差点のポイントを見つけることです。

例えば：

交差点

指定されたリスト A と B について、A と B は点c1で「出会い/交差」し、上記のアルゴリズムは を返しc1ます。OPがOPがアクセスできない、Hashmapsまたは何らかの種類のものにアクセスできないと述べたように、OPはアルゴリズムにO(1)スペースの複雑さを持たせる必要があると言っていると思います。

興味があれば、少し前に Leetcode からこのアイデアを得ました: Intersection of Two Linked Lists。

于 2021-06-29T14:41:18.413 に答える