0

d_arraysに格納されている可変量のジェネリック配列を取り、それらの間ですべての一意の要素 (1 回だけ発生する要素) を収集し、それらを という配列に格納するアルゴリズムを作成しようとしていますd_results。たとえば、配列は次のとおりです。

int intA[] = { 12, 54, 42 };
int intB[] = { 54, 3, 42, 7 };
int intC[] = { 3, 42, 54, 57, 3 };

d_results内容を含む配列を生成します{ 12, 7, 57 }。

プロセスの現在のアルゴリズムは次のとおりです。

template <class T>
inline
void UniqueTableau<T>::run() {
    T* uniqueElements = d_arrays[0];
    int count = 0;
    for (int i = 1; i < d_currentNumberOfArrays; ++i) {
        if (count == 0) {
            uniqueElements = getUnique(uniqueElements, d_arrays[i], d_sizes[i - 1], d_sizes[i]);
            ++count;
        }
        else {
            uniqueElements = getUnique(uniqueElements, d_arrays[i], d_numberOfElementsInResult, d_sizes[i]);
        }
    }
    d_results = uniqueElements;
}

template <class T>
inline
T* UniqueTableau<T>::getUnique(T* first, T* second, int sizeOfFirst, int sizeOfSecond) {
    int i = 0;
    int j = 0;
    int k = 0;
    T* uniqueElements = new T[sizeOfFirst + sizeOfSecond];
    while (i < sizeOfFirst) {    // checks the first against the second
        while ((first[i] != second[j]) && (j < sizeOfSecond)) {
            ++j;
        }
        if (j == sizeOfSecond) {
            uniqueElements[k] = first[i];
            ++i;
            ++k;
            j = 0;
        } else {
            ++i;
            j = 0;
        }
    }
    i = 0;
    j = 0;
    while (i < sizeOfSecond) {    // checks the second against the first
        while ((second[i] != first[j]) && (j < sizeOfFirst)) {
            ++j;
        }
        if (j == sizeOfFirst) {
            uniqueElements[k] = second[i];
            ++i;
            ++k;
            j = 0;
        } else {
            ++i;
            j = 0;
        }
    }

    T* a = new T[k];    // properly sized result array
    for (int x = 0; x < k; ++x) {
        a[x] = uniqueElements[x];
    }

    d_numberOfElementsInResult = k;
    return a;
}

d_sizesは の各配列のサイズを保持する配列でありd_arrays、d_numberOfElementsInResultは の要素数ですd_results。

さて、この配列が行っていることは、一度に 2 つを比較し、それら 2 つの固有の要素を取得し、それらの要素を次の配列と比較するなどです。問題は、これを行うと、たとえば、3 番目の配列と最初の 2 つの一意の要素の間では一意であるが、3 番目と最初の配列の間では一意ではない要素がある場合があることです。これは紛らわしい表現なので、上記の配列を使用した視覚的な例を次に示します。

最初に、アルゴリズムは 1 番目と 2 番目の配列の一意の要素を見つけます。

{ 12, 3, 7 }

次に、これを 3 番目の配列と照合して、それらの間の一意の要素を生成します。

{ 12, 7, 42, 54, 57 }

右？違う。ここでの問題は、42と54が一意の配列に表示されないため、3 つの配列すべてに共通であるにもかかわらず、それらが最終製品になってしまうことです。

誰でもこれに対する解決策を考えることができますか? このアルゴリズムの変更が推奨されますが、それが不可能な場合、この問題に取り組む別の方法は何ですか?

4

3 に答える 3

2

編集: 指摘したように、アルゴリズムは O(nlogn) 時間と O(n) 空間の複雑さです。

すべての配列内の各要素のトラバースを実行し、トラバースされた各アイテムのカウントのマップを形成します。

マップが作成されたら、それを繰り返し処理し、カウントが 1 である要素の配列を形成します。

于 2013-11-02T02:30:56.280 に答える
0

メモリが問題であり、別の方法でこれを行いますが（経験不足のため？） - 実際、投稿されたばかりの答えを考えていました！

とにかく、複製を破棄して二次配列に保存しないでください。この配列を取得して、新しい配列ごとに 2 回追加すると、アルゴリズムをほとんど変更できなくなります。唯一の変更点は、重複を作成し、毎回より大きなリストを調べることです。ただし、これにより時間とメモリが追加されます。それが懸念される場合は、最初に投稿された回答を使用してください。

于 2013-11-02T02:45:44.860 に答える
0

解決策 1:

  1. すべての配列のすべての要素を 1 つに入れるだけです。
  2. 配列をソートする
  3. 重複を削除します。

解決策 2:

  1. キーが要素で値がブール値であるマップを作成します
  2. 個々の配列をトラバースするだけです。要素がマップに存在しない場合は、キーを要素として、値を true として配置します。ただし、要素が既に存在する場合は、値を false にします。
  3. ここで、値の部分が true であるマップから要素を出力するだけです。つまり、一度発生しただけです。

なぜ私は整数ではなくブール値として値を入れているのですか:

既知のように、マップにキーの形式の要素が存在する場合、その要素が配列に存在することを示します。そのため、次に要素が再度見つかったときに false にすると、重複が表示されます。ご理解いただければ幸いです。

于 2013-11-02T04:33:04.520 に答える