1

私はこの問題に遭遇しました：

数値の 2 つの配列が与えられた場合、2 つの配列のそれぞれが同じ整数のセットを持つかどうかを調べます。N * log(N)余分なスペースがない場合よりも高速に実行できるアルゴリズムを提案してください。

ここにリンクがあります

2 つの配列が同じ整数のセットを含む場合の検索

アルゴリズム-to-tell-if-2-arrays-have-identical-members

しかし、上記のリンクからすべての回答を読んだ後、私が遭遇したこの簡単な回答が見つかりませんでした.ここにあります....

int main(){
    int a[] = {1,5,5,7,5,6,6};
    int b[] = {1,6,6,5,7,5,9};

    int i = 0;
    int size = 0;
    int xor_ab = a[0]^b[0];
    int sumDiff_ab = (a[0] - b[0]);;

    if(sizeof(a)/sizeof(a[0]) == sizeof(b)/sizeof(b[0])){
        size = sizeof(a)/sizeof(a[0]);
    }else{
        printf("not identical : array size differ");
        return 0;
    }

    for(i=1; i < size ; ++i){
        xor_ab = xor_ab ^ a[i] ^ b[i];
        sumDiff_ab += (a[i] - b[i]);
    }
    if(xor_ab == 0 && sumDiff_ab == 0){
        printf("identical");
    }else{
        printf("not identical");
    }
    return 0;
}

今、私のソリューションがすべてのユースケースで機能するかどうかを知りたいです。そうでない場合は、そのようなユースケースを教えてください。

[編集]

配列内のすべての数値が +ve であると考えてください。

[受け入れられた回答]

@Boris Strandjevの回答を受け入れました。

私の解決策は、次のような場合には機能しません

{3,5}

{1,7}

4

3 に答える 3

4

アルゴリズムが機能しない例を次に示します。

a[] = {3, 5};
b[] = {1, 7};

2 つの配列から計算された 2 つの値 - あまりにも多くの異なる配列セットが同じ 2 つの値に評価されます。このようなアイデンティティの比較は決して機能しません (発生するすべての衝突を考慮してください)。

于 2013-09-21T10:57:05.180 に答える
0

質問の答えにはならないかもしれませんが、ハッシュ関数を使用して配列を比較するのはどうでしょうか?

#include <stdio.h>
#include <stdlib.h>
#include <openssl/sha.h>
int main(){
    int a[] = {1,5,5,7,5,6,6};
    int b[] = {1,5,5,7,5,6,6};

    unsigned char hasha[SHA_DIGEST_LENGTH]; // == 20
    unsigned char hashb[SHA_DIGEST_LENGTH]; // == 20

    SHA1((char*) a , sizeof(a), hasha);
    SHA1((char*) b , sizeof(b), hashb);

    printf("Are arrays equals ? %d\n" , (strcmp(hasha,hashb)==0? 1:0));

    return 0;
}

そして、あなたはそれをコンパイルすることができます:

 gcc test.c -lssl -lcrypto -o test
于 2013-09-21T11:25:12.263 に答える