0

今天早些时候我问了类似的问题来找到两个数组中常见的最大元素。我在这里得到了几个很好的解决方案（找到两个数组中常见的最大元素？）。

现在我想到了，如果我们必须找到在 n 个不同数组中共有的最大元素而不是两个数组，该怎么办？

例子：

 array1 = [1,5,2,4,6,88,34]
 array2 = [1,5,6,2,34]
 array3 = [1,34]
 array4 = [7,99,34]

Here the maximum element which is common in all the arrays is 34.

单独创建 array1, array2 ..... array(N-1) 的哈希图，然后检查每个哈希图中 arrayN 的每个元素，以跟踪最大元素（当存在于所有哈希图中)?

我们能有比这更好的解决方案吗？

4

2 回答 2

1 
For each array A_n:
  Add all elements in A_n to a hashset, H_n

Create a hashmap, M, which maps values to counts.
For each hashset H_n:
  For each value, v, in H_n:
    M[v]++

Go through M for the highest value with count == N

这将在 O(n) 时间和空间中运行，其中 n 是所有数组中元素的总数。它还可以正确处理在单个数组中重复的元素，您没有提到，但这可能会导致某些算法出现问题。如果您知道单个数组中不会有重复元素，则可以跳过第一步，直接从数组中向 M 添加值。

于 2012-06-21T20:25:22.987 回答
0

hashmap 不利于跟踪最大元素。你想要的是一个最大堆或哈希集。

您创建 n 个最大堆并遍历其中的 n 个。您采用常见的最大元素。这可能很难实施。

另一种方法是找到所有集合的交集并从交集中获取最大值。在这种情况下，您可以使用 hashset。

于 2012-06-21T17:46:27.997 回答