文章/答案/技术大牛

发布

社区首页 >问答首页 >找到n个不同数组中常见的最大元素？

问找到n个不同数组中常见的最大元素？
EN

Stack Overflow用户

提问于 2012-06-22 01:43:10

回答 2查看 165关注 0票数 0

今天早些时候，我问了一个类似的问题来找出两个数组中常见的最大元素。我这里有几个很好的解决方案( Find the maximum element which is common in two arrays?)。

现在我想到，如果我们要找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.

创建array2的array1哈希图是不是一个好主意……数组(N-1)，然后检查每个哈希图中arrayN的每个元素，跟踪最大元素(当出现在所有哈希图中时)？

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

algorithm

回答 2

Stack Overflow用户

回答已采纳

发布于 2012-06-22 04:25:23

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添加值。

票数 1

Stack Overflow用户

发布于 2012-06-22 01:46:28

hashmap不适合跟踪max个元素。您需要的是最大堆或哈希集。

创建n个最大堆并遍历其中的n个。您可以使用公共的max元素。这可能很难实现。

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

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/11143760

复制

相似问题

问找到n个不同数组中常见的最大元素？
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问找到n个不同数组中常见的最大元素？EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问找到n个不同数组中常见的最大元素？
EN