如何检查两个大小相等的数组在 C 中是否具有相同的值？（复杂度 O(n) ）

Question

编辑：元素的取值范围从0到99从0到99。这可能吗？我试过使用下面的代码，但显然是错误的：

#include <stdio.h>

int scrambled(unsigned int a[], unsigned int b[], unsigned int len) {
    if (len = 0) {
        return 1;
    } else {
        int sumA, sumB, i;
        for (i = 0; i < len; i++) {
            sumA += a[i];
        }
        for (i = 0; i < len; i++) {
            sumB += b[i];
        }
        if (sumA == sumB) {
            return 1;
        } else {
            return 0;
        }
    }
}

我假设具有相同值和的两个数组也将具有相同的值，但事实并非如此。 {2,2} 和 {3,1} 总和相同，但值不同。

有什么方法可以检查，换句话说，一个数组是否是另一个具有线性复杂度时间的排列？

Answer 1

我不会说英语，也不是专业的开发人员

打赌我现在明白这个问题了。

我认为这个问题是你没有重置 'sumA'、'sumB' 变量

sumA 和 sumB 有垃圾值

我认为你会这样做

int sumA = 0, sumB = 0, i;

Answer 2

是的，在 C++ 中使用散列：

#include <iostream>
#include <unordered_set>

bool isEqual(int a1[], int a2[], int len) {
  using namespace std;
  unordered_set<int> s1(a1, a1 + len); //O(n)
  unordered_set<int> s2(a2, a2 + len); // O(n)
  return s1 == s2; // O(n)
}

int main() {
  using namespace std;
  int a1[5] = {5,2,3,4,1};
  int a2[5] = {1,3,2,5,4};
  std::cout << isEqual(a1, a2, sizeof(a1) / sizeof(int)) << std::endl;

  int a3[5] = {0,2,3,4,5};
  int a4[5] = {1,6,2,5,4};
  std::cout << isEqual(a3,a4, sizeof(a3) / sizeof(int)) << std::endl;
  return 0;
}

如果您的数据中存在相同的值，请将 unordered_set 交换为 unordered_multiset

此外： http://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp

Complexity Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.

更快速的计划：根据您的数据实现 custom 散列 table。例如，你的数据集的范围是多少？一个数组中有多少个数字？

Answer 3

如果数组中元素的值足够小，您可以保持零数组 arr 的大小等于数组中的最大值。然后对于一个数组 A 你可以遍历元素并将 arr 中对应的元素标记为 1。然后对于另一个数组 B，做同样的事情并检查 A 中是否有任何元素不在 B.

中

#include <stdio.h>
#define MAX 10000
int arr[10000];
int scrambled( unsigned int a[], unsigned int b[], unsigned int len)
{
    if (len=0)
    {
    return 1;
    }
    else
    {
        for (int i=0; i<len; i++)
        {
            arr[A[i]] = 1;
        }
        int same = 1;
        for (int i=0; i<len; i++)
        {
            if(arr[B[i]] != 1)
                same = 0;
        }
        if (same)
        {
            return 1;
        }
        else    
        {
            return 0;
        }
    }
}

Answer 4

如果可以修改数组，可以使用基数排序对它们进行排序，并使用简单的 for 循环进行比较。基数排序的时间复杂度为 O(N*log(maxN))，其中 maxN 是数组中任意数字的最大值。对于 unsigned int 的数组，这个最大值是常数，因此时间复杂度为 O(N).

如何检查两个大小相等的数组在 C 中是否具有相同的值？（复杂度 O(n) ）

How to check if two arrays of equal size have the same values in C? (complexity O(n) )

c

arrays

permutation

如何检查两个大小相等的数组在 C 中是否具有相同的值？ （复杂度 O(n) ）

How to check if two arrays of equal size have the same values in C? (complexity O(n) )

c

arrays

permutation

如何检查两个大小相等的数组在 C 中是否具有相同的值？（复杂度 O(n) ）