0

私は数時間頭をかいていて、助けを借りることができました...

オブジェクトのリストが3つあります。各リストには同じオブジェクトを含めることができます（ただし、含める必要はありません）。各リストに少なくとも1つの一意のオブジェクトがあるかどうかをテストするアルゴリズムが必要です。

編集：アイテムは各リストに1回だけ含めることができますが、複数のリストに含めることができます。

編集：疑似4番目のリストがあります-3つのリストのそれぞれから1つのアイテム。それはユニークを含まなければならないリストです。各リストには、全体で3つのアイテムが含まれる可能性があります。4番目のリストには一意のものが含まれている可能性があるため、これはtrueを返すはずです。

編集：これは私がこれまでに思いついたものですが、これがどれほど効率的であるか、またはそれが機能するかどうかはわかりません！

bool Uniques( List<Item> list1, List<Item> list2, List<Item> list3 ) {
    foreach( Item item1 in list1 ) {
        foreach( Item item2 in list2 ) {
            if ( item1!=item2 ) {
                foreach( Item item3 in list3 ) {
                    if ( item3!=item1 && item3!=item2 ) return true;
                }
            }
        }
    }
    return false;
}

編集：説明のために、ここに例があります。
色の全体的なリストから：赤、緑、青、黄、シアン、マゼンタ、白、黒、オレンジ、紫。

リスト1には赤が含まれ、緑
リスト2には赤が含まれます
リスト3には青が含まれ、オレンジ
はFALSEになります

リスト1には赤、緑が含まれ
ていますリスト2には赤、緑が
含まれていますリスト3には赤、緑が含まれてい
ます結果はFALSEになります

リスト1には赤、緑が含ま
れていますリスト2には黄色が含まれています
リスト3には赤、緑が含まれています
結果はTRUEになります

4

3 に答える 3

2

編集：元の質問を誤解しているため、基本的に回答を変更しています。

各リスト要素はそのリスト内で一意であることがわかっているため、次のアルゴリズムを使用できます。

Compute the length of the three lists.
Sort these lengths into a tuple (l_1,l_2,l_3) in ascending order.

If l_1 >= 1 and l_2 >= 2 and l_3 >= 3, then answer 'YES'; 
else, 
    if among all possible combinations there is a valid one, 
    then, return 'YES', 
    otherwise return 'NO'.

リストの長さが事前にわかっている場合、このアルゴリズムには一定の時間がかかります (それ以外の場合は線形です)。考えられるすべての組み合わせを調べる場合、調べるトリプルは 6 つ未満であることに注意してください。

さて、これが機能することの証明は非常に簡単です: length のリストから要素を選択し、次にx_1length のリストから要素を選択します(これは 以来可能です)。ここで、 length のリストから、 と とは異なる要素を選択します。ここでも、リストには少なくとも 3 つの異なる要素があるため、そのような要素を選択できます。l_1x_2l_2x_1l_2 >= 2x_3l_3x_1x_2

あなたが求めていた問題を実際に解決したことを願っています。

于 2013-02-04T21:20:47.437 に答える
0

線形時間: ハッシュを使用します。最初に、リスト 1 の各 elt を 3 つのブール値の配列にハッシュし、最初のブール値を true に設定します。リスト 2 と 3 について繰り返します。ほら、キーが要素で、値が各要素が属するリストを示すハッシュができました。

次に、各リストに一意のアイテムが少なくとも 1 つあるかどうかを確認するために、ハッシュ値をループ処理して、3 つのブール値のうち 1 つだけが true に設定されている配列をチェックします。たとえば、値が [true, true, false] の場合は無視しますが、一方の値が [false, true, false] の場合、2 番目のリストには一意のアイテムがあることがわかります。

于 2013-02-04T21:09:24.470 に答える
0 
set counter = 0
create empty list U
for each list L
    create D, a duplicate of list L
    for each list P, where P != L
        remove all items in P from D

    add all items in D to U
    if D is not empty, increment counter


if counter == number of lists, return U, else return empty list

各リストに他のリストにない値が含まれている場合にのみ、返されるリストは空ではありません。空の場合は、そのような共有されていない値のセットです。

于 2013-02-04T22:07:51.767 に答える