1

我遇到了这个问题：

给定两个数字数组，找出这两个数组中的每一个是否具有相同的整数集。N * log(N)建议一种比没有额外空间运行得更快的算法。

链接在这里

查找如果两个数组包含相同的整数集

判断两个数组是否具有相同成员的算法

但是在阅读了上述链接的所有答案之后，我没有找到我遇到的这个简单的答案，这里是......

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};

从两个数组中计算出的两个值 - 太多不同的数组集将评估为相同的两个值。这种身份比较永远不会起作用（考虑将发生的所有冲突）。

于 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 回答
0

这适用于 a[] 和 b[] 的有限大小以及 a[] 和 b[] 中值的有限范围：

#include <stdio.h>

unsigned primes[] = {1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
                ,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149 };

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

#if SHOULD_BE_EQUAL
unsigned b[] = {1,5,5,6,7,5,6};
#else
unsigned b[] = {1,6,6,5,7,5,9};
#endif

#define COUNTOF(x) (sizeof x / sizeof x[0])

unsigned pa, pb, idx;

for (pa=1,idx=0 ; idx < COUNTOF(a); idx++) pa *= primes[a[idx]];
for (pb=1,idx=0 ; idx < COUNTOF(b); idx++) pb *= primes[b[idx]];

printf("A[] and b[] are %s equal\n", (pa==pb) ? "completely" : "not" );

return 0;
}
于 2013-09-21T11:40:57.957 回答