3

異なるサイズの n セットの整数が与えられます。各セットには、複製を含めることもできます。集合の交点を見つけなければなりません。要素がすべてのセットに複数回存在する場合は、結果に追加する必要があります。

たとえば、3 つのセット {0,5,5,3,4} {5,2,3,5,6} {1,3,5,5,6} があるとします。指定されたセットの交点は {3,5,5} である必要があります

私のアプローチは次のとおりです。

1.配列を並べ替えます。

2.最小の配列から始まるすべての要素を比較し、カウントを更新します。

交差点を見つけるためのより効率的なアプローチはありますか?

4

5 に答える 5

3

「セット」に小さな整数しか含まれていない場合、それらはカウントの配列で表すことができます...たとえば、{5,2,3,5,6} は

index 0 1 2 3 4 5 6
count 0 0 1 1 0 2 1

そのようなセットの交点は、カウントの最小値です。

      index 0 1 2 3 4 5 6
            -------------
{0,5,5,3,4} 1 0 0 1 1 2 0
{5,2,3,5,6} 0 0 1 1 0 2 1
{1,3,5,5,6} 0 1 0 1 0 2 1  
min         0 0 0 1 0 2 0 = {3,5,5}

値が短整数ではなく、数が少ない場合は、値の配列を保持します。これは、値と配列のインデックスである短整数の間のマップとして機能します。

値が多すぎて各セットのカウントの配列を持つのがコストがかかりすぎる場合は、値からカウントへのマップを使用して、値の配列とともに各「セット」を表します...次に、配列を反復処理して生成します各値、マップを反復処理してカウントを取得し、最小値を計算します。このためには、ハッシュ テーブルまたはバイナリ ツリー ライブラリを使用してマップを実装する必要があります... または、当然のことながら、そのようなコレクション型を提供する C よりも多くの最新の言語のいずれかを使用します。

于 2013-03-28T08:11:47.043 に答える
0

これが私のコードです。C99でコンパイルします（最初にget、insert、remove関数を実装することを忘れないでください）：

struct MyNode { MyNode * next; int value; int frequency; }

// returns MyNode pointer when value exist
MyNode * get(MyNode * head, int val);

// insert a new value, with frequency = 1
void insert(MyNode * head, int val);

// remove an element from the linked-list
bool remove(MyNode * head, int val);

int * intersection (int ** set, int w, int * h)
{
    MyNode * head = 0;
    MyNode * temp = 0;
    int finalSize = 0;
    int k = 0;

    for (int i=0; i<w; i++)
    {
        for (int j=0; j<h[i]; j++)
        {
            temp = get(head, set[i][j]);

            if (temp == 0)
            {
                insert(head, set[i][j]);
                finalSize++;
            }
            else
            {
                temp->frequency++;
            }
        }
    }

    temp = head;
    while (temp != 0)
    {
        if (temp->frequency != w)
        {
            temp = temp->next;
            remove(head, temp->value);
            finalSize--;
        }
        else
            temp = temp->next;
    }

    int * intersection = (int*)malloc(finalSize*sizeof(int));

    temp = head;
    while (temp != 0)
    {
        intersection[k++] = temp->data;
        temp = temp->next;
    }

    return intersection;
}
于 2013-03-28T05:59:59.820 に答える
0

たとえば、配列ごとに辞書を作成し、各配列をトラバースしてカウンターに追加し、新しい数値が検出された場合の「グローバル」辞書に追加することができます。次に、「グローバル」辞書から次の番号を選択し (カウンター辞書の少なくとも 1 つに存在することが保証されています)、すべてのカウンターの最小値を取得します。もちろん、1 つのディクショナリで null が検出された場合、この数値は結果に追加されません。それ以外の場合は、結果の配列に「見つかった最小」量の「数値」を追加します。このようなディクショナリ構造では、アルゴリズムの完全な複雑さは、O(n*m)M がセットのサイズの最大値であり、N がその量であるということです。一方、セットを並べ替えると、O(n*m*log(m))

于 2013-03-28T05:38:01.920 に答える
0

あなたのソリューションに提案する唯一の最適化は、キーが配列の要素になり、値が発生。テストの例: {0,5,5,3,4} {5,2,3,5,6} {1,3,5,5,6} 辞書は次のようになります

{0 => 1, 3 => 1, 4 => 1, 5 => 2}
{2 => 1, 3 => 1, 5 => 2, 6 => 1}
{1 => 1, 3 => 1, 5 => 2, 6 => 1}

次に、最小の辞書から始めて辞書のペアを比較し、要素が両方に出現する場合は、出現回数が少ない方を採用します。この最適化により、重複の処理に必要な時間を節約できます。

結果の辞書は次のようになります: {3 => 1, 5 => 2} - 変換して配列に戻すことができます。

于 2013-03-28T08:18:23.847 に答える