假设有10列，我们必须找出给定数组所有公共元素。

suppose there are 10 arrays and we have to find out all the common elements in given arrays.

目前我选择第一阵列和第一阵列中通过所有其余的阵列i循环的每个元件，但是这会增加时间复杂度。

Currently I am selecting first array and for each element in the first array i loop through all the remaining arrays, but this increases time complexity.

有没有什么好的算法与比较最小没有做到这一点？

Is there any good algorithm to do it with minimum no of comparisons ?

推荐答案

我假设你想要的阵列的交集。

基于散列的方法：

此假设每个数组中的独特元素。

This assumes unique elements in each individual array.

插入第一个数组中的所有元素融入元素的哈希映射来算，与数以1开始了。

Insert all the elements in the first array into a hash map of element to count, with count starting off at 1.

然后通过其余阵列迭代，递增每遇到元件的计数。

Then iterate through the remaining arrays, incrementing the count of each encountered element.

最后，输出全部用数等于阵列的多个元素。

At the end, output all elements with counts equal to the number of arrays.

您可以在C ++ 11使用词典 C＃或 unordered_map 。你也可以使用一个有序映射在这里（如地图在C ++中）。

You can use Dictionary in C# or unordered_map in C++11. You can also use a sorted map here (e.g. map in C++).

基于排序方式：

排序的所有单独的阵列。

Sort all the arrays individually.

遍历所有的阵列的同时，保持了堆或二叉搜索树包含从每个数组的一个元素。在每个步骤，从结构上除去最小值和从阵列，其中该元件位于添加的下一个元素

Iterate through all the arrays at the same time, maintaining a heap or binary search tree containing one element from each array. At each step, remove the minimum from the structure and add the next element from the array where that element was located.

每当最小=最大值，输出该值。

Whenever the minimum = the maximum, output that value.

我的猜测是，这可能是非常相似， set_intersection 一样。

My guess is that this is probably very similar to what set_intersection does.

要应付每个阵列中的非唯一值： （即 1 2 2 3 4 和 2 2 4 5 应该输出 2 2 4 ）

To deal with non-unique values in each individual array: (i.e. the 'intersection' of 1 2 2 3 4 and 2 2 4 5 should output 2 2 4)

您需要记住，当你最后一次输出值，只输出你插入一个数字数组的元素数量大于或等于后一个值。

You need to remember when the last time you output a value was and only output a value after you've inserted a number of elements greater than or equal to the number of arrays.

如果你不这样做，你会得到很多次了太多的结果。看相交的一个简单的例子 1，1 和 1，1 和 1，1 。预期的输出是 1，1 ，但会发生这种情况：

If you don't do this, you'd get many times too many results. Look at a simple example of intersecting 1, 1 and 1, 1 and 1, 1. The expected output is 1, 1, but this would happen:

在结构： 1，1，1 最小=最大值= 1，输出 1 删除1那是在第1个数组，然后插入第二个1 在结构上： 1，1，1 最小=最大值= 1，输出 1 删除1那是在第2个数组，然后插入第二个1 在结构上： 1，1，1 最小=最大值= 1，输出 1 删除1那是在第3阵列，并插入第​​二个1 在结构上： 1，1，1 最小=最大值= 1，输出 1

In structure: 1, 1, 1 Min = max = 1, output 1 Remove 1 that was in 1st array and insert 2nd 1 In structure: 1, 1, 1 Min = max = 1, output 1 Remove 1 that was in 2nd array and insert 2nd 1 In structure: 1, 1, 1 Min = max = 1, output 1 Remove 1 that was in 3rd array and insert 2nd 1 In structure: 1, 1, 1 Min = max = 1, output 1

现在输出的是 1，1，1，1 。

在插入时，请确保您始终都具有同等价值后，将其插入（即把它当作大于它们）。要做到这一点，你可以简单地有一个自动递增的唯一ID作为次要的比较值。

When inserting, make sure you always insert it after all other equal values (i.e. treat it as greater than them). To do this, you can simply have an auto-incremented unique ID as a secondary comparison value.

如果你不这样做，你可以保持在同一阵列，这将很快让你一个不同的元素删除元素，因此你不一定会输出正确数量的非唯一值。

If you don't do this, you can keep removing elements from the same array, which would quickly get you to a different element, thus you won't necessarily output the right number of non-unique values.

作为一个例子，如果我们相交 1，1，1，2 和 1，1，1 ，你可以只是碰巧从第一阵列重复地移动，渐渐 2 3个步骤，但是，由于上述观点，我们只输出每2个步骤，所以我们' ð只有2个，而不是3 1 的。

As an example, if we intersect 1, 1, 1, 2 and 1, 1, 1, you can just happen to repeatedly remove from the first array, getting to 2 in 3 steps, but, because of the above point, we only output every 2 steps, thus we'd only have 2 instead of 3 1's.