检查两个数组是否相似[重复]

This question already has an answer here:

这个问题已经有了答案:

Check if 2 arrays are similar without hashing or sorting 4 answers
检查2个数组是否相似，而不进行散列或排序4个答案
Check if array B is a permutation of A 9 answers
检查数组B是否为9个答案的排列

Given two arrays, check if they're similar (i.e. have the same integers and each integer occurs same number of times).

给定两个数组，检查它们是否相似(例如，具有相同的整数，每个整数出现的次数相同)。

For example:

例如:

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

I was not allowed to use sorting and hashtable. It should be O(n) and should not use any extra space.

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

This was an interview question.

这是一个面试问题。

Tried with rules like:

尝试与规则:

Sum of integers in two arrays should be same
两个数组中的整数和应该是相同的
Product of integers in two arrays should be same.
两个数组中的整数的乘积应该是相同的。
XOR of all integers should be zero
所有整数的XOR都应该是零。

But still interviewer is not happy. Maybe I'm missing some corner cases.

但面试官还是不开心。也许我漏掉了一些特例。

4 个解决方案

#1

I can think of one way to perform this task, if the elements values are integers and bounded by n (1...n), where n is the size of the arrays (this applies to you example):

我可以想出一种执行此任务的方法，如果元素值是整数，并且以n(1…n)为界，其中n是数组的大小(这适用于您的示例):

In each array, for each element x, we do arr[x%(n+1)-1] += n+1. we use mod since the element may vary through the process, by using mod we get the element that appeared in the original array.

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

What we do is count the number of appearances of a value v in arr[v] by adding n+1, then we can get the original value by doing arr[v]%(n+1) as the value is bounded by n, and the number of appearances by doing arr[v]/(n+1).

我们要做的是通过增加n+1来计算一个值v在arr[v]中的出现次数，然后我们可以通过做arr[v]%(n+1)来得到原始值，因为这个值以n为界，通过做arr[v]/(n+1)来得到出现次数。

In the end we compare the number of appearances of each value in A and B, if for any value they are different, we return false. if the counting was the same for all the values, we return true.

最后，我们比较A和B中每个值的出现次数，如果它们是不同的，我们返回false。如果所有值的计数相同，则返回true。

This is an O(n) time solution that requires O(1) memory.

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

Here's the algorithm:

这里的算法:

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

#2

Try this Algorithm in JavaScript :

用JavaScript试试这个算法:

DEMO

演示

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

#3

Probably he means that you should compare sum by i of f(x[i]) and sum by i of f(y[i]), where x and y are the arrays, f is a hash function.

也许他的意思是，你应该比较和i (f(x[i])和和i (f(y[i])，其中x和y是数组，f是一个哈希函数。

#4

There are two possible ways for the first array whether it contains non repeated elements or not. let's say for simplicity the first array doesn't contain repeated elements, then the idea is very simple track the total as in my following code

对于第一个数组，不管它是否包含非重复元素，有两种可能的方法。为了简单起见，我们说第一个数组不包含重复的元素，那么我们的想法是非常简单地跟踪总数，如下面的代码所示

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

If the total is less than or greater than 5, then the arrays are not same. Now, it seems to me that we need to come up with an algorithm that calculates the proper total, so we need a function that accepts an array and check the total number. For example, in your case the total number should be 9 (1 for 3, 4 for 2, and 4 for 5). This is what came up to my mind. I hope the idea is clear. This is what I did for a general case

如果总数小于或大于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;
}

Another approach with using one loop. the idea is to get the total of an array and then divide the total by each element to get new total. If the new total of the first array is equal to the new total of the second array then, they are same. (Note: I haven't tested my code for all cases; however, my approach seems sensible to me.

使用一个循环的另一种方法。我们的想法是得到一个数组的总数，然后除以每个元素的总数得到新的总数。如果第一个数组的新总数等于第二个数组的新总数，那么它们是相同的。(注意:我没有对所有的情况进行代码测试;然而，我的方法似乎是合理的。

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

#1