在C中获取两个数组的差异的有效方法是什么？

样本输入

Array_1 [] = { 10, 20, 30, 40, 50 }; Array_2 [] = { 30, 40, 50, 60, 70 }; 

样本输出

 Array_1_Extras [] = { 10, 20 }; Array_2_Extras [] = { 60, 70 }; 

描述

1. 输入数组未排序。

2. 输入数组长度 – 10K。

3. 输入数组值范围为0 – 4095。

4. 不应修改输入数组顺序和值。

5. 输出数组可以按任何顺序排列。

6. 输出数组中不需要重复项。

我需要一些时间有效的逻辑来实现这个程序。 提前致谢。

Answer 1

这是一个简单的O(N)时间算法，有点占用空间（它也考虑了重复）。

1）声明一个长度为4096的零的数组C
2）迭代第一个数组A ，对于索引的每个元素， i 增加 C[A[i]]
3）迭代第二个数组B ，并且对于每个元素， i 减少 C[B[i]]
4）迭代C和i的负C[i]将表示B - A的元素，而正的A - B将表示A - B的元素
*如果您感兴趣，绝对值将表示欺骗号码的差异。

Answer 2

这是一个O（n）实现：

 int seen[4096]; memset(seen, 0, sizeof(seen)); int a[10000], b[10000]; size_t aSize, bSize; ... // Fill a and b for (size_t i = 0 ; i != aSize ; i++) { seen[a[i]] |= 1; } for (size_t i = 0 ; i != bSize ; i++) { seen[b[i]] |= 2; } size_t j = 0; for (size_t i = 0 ; i != aSize ; i++) { if (seen[a[i]] == 1) { a[j++] = a[i]; } } aSize = j; j = 0; for (size_t i = 0 ; i != bSize ; i++) { if (seen[b[i]] == 2) { b[j++] = b[i]; } } bSize = j; 

无论计数如何，此方法都会删除b中也包含b所有数字。 它也保留重复。 例如，如果输入是这样的

 a = [10, 10, 10, 20, 20, 20, 30 , 40] b = [10, 30, 40, 40, 40, 40, 50] 

输出将是

 a = [20, 20, 20] b = [50] 

Answer 3

对于大小为10000的输入数组，您很可能能够通过一般算法的渐近复杂度来判断。

朴素算法是迭代一个数组，扫描另一个数组的外观，然后反转角色并再次执行。 如果较长arrays的大小与较短arrays的大小的比率是O(1) ，则该方法的成本受O(n 2 ) 。

您可以通过创建输入数组（ O(n) ）的副本，对它们进行排序（ O(n log n) ）以及对已排序数组执行一次联合线性扫描来解决O(n log n)成本问题，类似到合并排序的合并步骤（ O(n) ）。

但是，假设输入数组的值是从相对较小的范围中提取的，那么考虑整体为O(n)的解决方案是合理的：

1. 每个可能的输入数组值创建一个具有一个2位或更宽位域元素的数组
2. 扫描第一个输入数组; 对于每个值，设置对应于该值的位域的位0
3. 扫描第二个输入数组; 对于每个值，设置对应于该值的位域之一
4. 扫描位域数组：元素告诉您相应的输入值是出现在两个输入数组中，恰好是一个，还是两个都不出现。

Answer 4

1. 对数组进行排序（如果无法更改原件，则为副本）
2. 递归地走他们，直到他们完成

对于每个递归，取每个数组的第一个元素。

一个。 如果它们不同，则将较小的数组添加到array_1_extras或array_2_extras并使用该元素前进数组
湾 如果他们是平等的，请注意重复并推进两个arrays