確定兩套整數是否相同，比

Question

我碰到這個問題就來了N日誌（N）速度快：

鑑於兩個數字陣列，發現如果每兩個數組中具有相同的一組整數。建議一種算法，其運行速度可以快於N * log(N)，不需要額外的空間。

這裏是鏈接

find-if-two-arrays-contain-the-same-set-of-integers

algorithm-to-tell-if-two-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; 
} 

Now我想知道，我的解決方案是否適用於所有用例。 如果沒有，請讓我知道這樣的用例。

[編輯]

請考慮所有數字+已經在數組中。

[接受的答案]

我接受@Boris Strandjev的答案，

我的解決方案將爲情況下，像

{3,5}不行

{1 ，7}

Answer 1

下面是一個算法不起作用的例子：

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

從兩個數組中計算出的兩個值 - 太多不同的數組集合將評估爲相同的兩個值。這種身份比較將永遠不會奏效（考慮將發生的所有衝突）。

Answer 2

也許這不會回答你的問題，但使用散列函數來比較數組呢？

#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 

Answer 3

這適用於尺寸有限的一個[]和b []，並在[]和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; 
}