检查2个数组是否具有相同的内容,忽略顺序,没有排序.什么是最有效的算法

Question

乱码的数组示例应返回1:

a = {10,15,20}, b = {10,15,20}
a = {99}, b = {99}
a = {1,2,3,4,5}, b = {5,3,4,2,1}
a = {}, b = {} (i.e. len = 0)
a = {2,1,3,4,5}, b = {1,2,4,3,5} 

乱码的数组示例应返回0:

a = {1,1}, b = {1,2}
a = {10,15,20}, b = {10,15,21}
a = {1,2,3,4,5}, b = {5,3,4,2,2} 

我在C中的代码是这样的,但它是一个O(N ^ 2)效率不高.

int scrambled( unsigned int a[], unsigned int b[], unsigned int len )
{
    int count1 = 0;
    int count2 = 0;

    for (int i=0; i< len; i++)
    {
        for (int j=0;j<len; j++)
        {
            if (a[i]==b[j])
            {
                count1++;
                break;
            }       
        }

        for (int j=0; j<len; j++)
        {
            if (b[i]==a[j])
            {
                count2++;
                break;
            }
        }
    }

    return (count1 == len && count2 == len );


}

以上代码存在缺陷.这有线性解决方案吗？

Answer 1

这是一个可以用O(n)复杂度实现的解决方案:

1. 为每个数组创建一个哈希映射.关键是数组元素.该值是出现的次数.
2. 迭代第一个哈希映射的键,并检查两个哈希映射的值是否相同.
3. 如果所有值都相同,则数组相等.