arrays - 检查两个数组是否相似

Question

给定两个数组，检查它们是否相似（即具有相同的整数并且每个整数出现相同的次数）。

例如：

int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}

我不允许使用排序和哈希表。它应该是 O(n) 并且不应该使用任何额外的空间。

这是一道面试题。

尝试使用以下规则：

1. 两个数组中的整数之和应该相同
2. 两个数组中整数的乘积应该相同。
3. 所有整数的异或应为零

但是面试官还是不高兴。也许我错过了一些极端情况。

Answer 1

我可以想到一种执行此任务的方法，如果元素值是整数并以n( 1...n)为界n，数组的大小在哪里（这适用于您的示例）：

在每个数组中，对于每个元素x，我们都这样做arr[x%(n+1)-1] += n+1。我们使用 mod 因为元素可能会在整个过程中发生变化，通过使用 mod 我们得到出现在原始数组中的元素。

我们所做的就是通过加法来计算一个值v在中出现的次数，然后我们可以通过do 得到原始值，因为该值是有界的，并且通过do 得到出现的次数。arr[v]n+1arr[v]%(n+1)narr[v]/(n+1)

最后我们比较每个值在A和中出现的次数B，如果对于任何值它们不同，我们就返回false。如果所有值的计数都相同，则返回true.

这是一个O(n)需要O(1)内存的时间解决方案。

这是算法：

bool checkIfArraysAreSimilar(int[] A, int[] B)
{
    n = A.length; // = B.length
    int i;

    for (i = 0; i < n; i++)
    {
        A[(A[i]%(n+1))-1] += n+1;
        B[(B[i]%(n+1))-1] += n+1;
    }

    for (i = 0; i < n; i++)
    {
        if (A[i] / n+1 != B[i] / n+1)
            return false;
    }

    return true;
}

Answer 2

在 JavaScript 中试试这个算法：

演示

var arr11 = [ 3, 5, 2, 5, 2]
var arr22 = [ 2, 3, 5, 5, 2]
console.log(arraySimilar(arr11,arr22));
function arraySimilar(arr1,arr2){ 
    var tempArr = arr2;
    // Checking Length if both the arrays are equal 
    if(arr1.length == arr2.length){
        //Running a For Loop for first array 
        for(i=0; i<arr1.length; i++){
            //If the Element is present removing from "tempArr"
            if(tempArr.indexOf(arr1[i])!= -1){
                tempArr.splice(tempArr.indexOf(arr1[i]),1);
            }
            else{ return false;}
        }
    }
    else{ return false; }
    // Check "tempArr" if it is empty
    if(tempArr.length==0){
        return true;
    }else{
        return false;
    }
}

Answer 3

可能他的意思是你应该比较 f(x[i]) 的 sum by i 和 f(y[i]) 的 sum by i，其中 x 和 y 是数组，f 是哈希函数。

Answer 4

第一个数组有两种可能的方式，无论它是否包含非重复元素。假设为简单起见，第一个数组不包含重复的元素，那么这个想法很简单，就像我下面的代码一样跟踪总数

#include <iostream>

int  main()
{ 
    int arr1[5] = { 1, 2, 3, 4, 5};
    int arr2[5] = { 5, 1, 3, 4, 2};

    int total(0);

    for (unsigned int i(0); i < 5; ++i)
    {
        for (unsigned int j(0); j < 5; ++j)
        {
            if ( arr1[i] == arr2[j] )
            {
                total += 1;
            }
        }
    }
    if ( total == 5 ) 
        std::cout << "Same " << std::endl;
    else 
        std::cout << "not Same " << std::endl;

    std::cin.get();
    return 0;
}

如果总数小于或大于 5，则数组不相同。现在，在我看来，我们需要提出一个计算正确总数的算法，因此我们需要一个接受数组并检查总数的函数。例如，在您的情况下，总数应该是 9（1 代表 3，4 代表 2，4 代表 5）。这就是我想到的。我希望这个想法很清楚。这是我为一般情况所做的

#include <iostream>


int getTotal(int arr[], const int size)
{
    int *temp = new int[size]; 
    int total(0);
    for (int i(0); i < size; ++i)
        temp[i] = arr[i];


    for (int i(0); i < size; ++i)
    {
        for (int j(0); j < size; ++j)
        {
            if ( arr[i] == temp[j] )
                total += 1;
        }
    }

    std::cout << total << std::endl;
    return total;
}

int  main()
{ 
    int arr1[5] = { 3, 5, 2, 5, 2};
    int arr2[5] = { 2, 3, 5, 5, 2};

    int total = getTotal(arr1, 5);
    int track(0);

    for (unsigned int i(0); i < 5; ++i)
    {
        for (unsigned int j(0); j < 5; ++j)
        {
            if ( arr1[i] == arr2[j] )
            {
                track += 1;
            }
        }
    }
    if ( track == total ) 
        std::cout << "Same " << std::endl;
    else 
        std::cout << "not Same " << std::endl;

    std::cin.get();
    return 0;
}

使用一个循环的另一种方法。这个想法是得到一个数组的总数，然后将总数除以每个元素以获得新的总数。如果第一个数组的新总数等于第二个数组的新总数，那么它们是相同的。（注意：我没有针对所有情况测试我的代码；但是，我的方法对我来说似乎是明智的。

#include <iostream>


double getTotal(double arr[], const int size)
{
    double total1(0), total2(0);

    for (int i(0); i < 5; ++i)
    {
        total1 += arr[i];
    }

    for (int i(0); i < 5; ++i)
    {
        total2 += total1/arr[i];
    }

    std::cout << total2 << std::endl;

    return total2;
}

int  main()
{ 
    double arr1[5] = { 3, 5, 2, 4, 2};
    double arr2[5] = { 2, 3, 5, 5, 2};

    double total1 = getTotal(arr1, 5);
    double total2 = getTotal(arr2, 5);

    if ( total1 == total2 ) 
        std::cout << "Same " << std::endl;
    else 
        std::cout << "not Same " << std::endl;

    std::cin.get();
    return 0;
}