什么是找到具有最高频率的数组中的元素最快的算法

我有两个输入数组X和Y我想回到与频率最高的发生在阵列Y.排列X该元素什么是找到具有最高频率的数组中的元素最快的算法

的这样做的天真方式要求对于数组X的每个元素x，我线性搜索数组Y的出现次数，然后返回频率最高的元素x。伪算法：

max_frequency = 0 
max_x = -1    // -1 indicates no element found 
For each x in X 
    frequency = 0 
    For each y in Y 
     if y == x 
      frequency++ 
    End For 
    If frequency > max_frequency 
     max_frequency = frequency 
     max_x = x 
    End If 
End For 
return max_x

由于有两个嵌套循环，该算法的时间复杂度为O（n^2）。我可以用O（nlogn）或更快的方式做到这一点吗？

来源

2013-03-23 nurabha

当讨论具有两个或更多维度的问题时，通常使用每个变量讨论复杂性是一个好主意。既然'X phs 2013-03-23 22:41:03

使用哈希表映射键来计数。对于数组中的每个元素，请像counts[element] = counts[element] + 1或您的语言等效。

最后，循环遍历哈希表中的映射并找到最大值。

来源

2013-03-23 21:16:34 cHao

为了清楚起见，那个时间复杂度是'O（X + Y）'，并且这里是最好的。 – phs 2013-03-23 22:39:07

可以做一个快速排序，然后用一个变量来计算一个数字中有多少个数字+这个数字是多少。这应该给你nlogn

来源

2013-03-23 21:13:08 rowdog

合并的鸿沟基于排序治理念为您提供了O（nlogn）复杂

来源

2013-03-23 21:13:55 apomene

或者，如果您可以有其他数据结构，您可以对数组Y进行遍历，以便每个数字在哈希表中更新其频率。这需要O(N(Y)时间。然后走X找到X中哪个元素的频率最高。这需要O(N(X))时间。总评：线性时间，因为你要看看这两个X和Y的各要素的任何实施至少一次（编辑：这不是严格在所有情况下讲真/所有的实现，为jwpat7指出，尽管在最坏的情况下它是真实的），你不能做得比这更快。

来源

2013-03-23 21:16:38 angelatlarge

这不是真的，你必须在任何实现中查看X和Y的每个元素至少一次。例如，假设我们计算Y中每个值的出现次数。如果f是Y中最频繁的元素，并且在通过X进行扫描时遇到f，则不需要查看X的其余部分。或者，如果X中的某个元素X0出现k次，只要Y的大小减去到目前为止所扫描的X元素的频率总和就低于k，我们就不需要考虑X的任何其他元素了。 – 2013-03-23 21:51:09

@ jwpat7：你说得对，我会纠正的。我在考虑平均/最坏的情况。现在你提出来了，还有其他的边界情况，例如当'X'包含一个元素时，或者如果你首先查看'X'，然后再查看Y，则可以停止查看'Y [n + 1 ]'如果你已经知道'Y [n]'是'Y'中最常见的元素，并且也是'X.' – angelatlarge 2013-03-23 22:06:15

的常见算法的时间复杂度列举如下：

Algorithm  | Best | Worst | Average 
--------------+-----------+-----------+---------- 
MergeSort  | O(n lg n) | O(n lg n) | O(n lg n) 
InsertionSort | O(n) | O(n^2) | O(n^2) 
QuickSort  | O(n lg n) | O(n^2) | O(n lg n) 
HeapSort  | O(n lg n) | O(n lg n) | O(n lg n) 
BinarySearch | O(1) | O(lg n) | O(lg n)

一般来说，通过列表遍历满足一定条件时，你真的不能做任何比线性时间更好。如果您需要对数组进行排序，我会坚持使用Mergesort（非常可靠）来查找数组中频率最高的元素。

注意：这是假设您想要使用排序算法。否则，如果您被允许使用任何数据结构，那么我会使用哈希表/散列表类型结构以及不断的查找时间。这样，您只需匹配键并更新频率键值对。希望这可以帮助。

来源

2013-03-23 21:17:37 David

遍历列表通常是在线性时间内完成的。除非你有一些真正的需要排序，许多情况下可以在O（N）中处理。 – cHao 2013-03-23 21:20:33

@cHao同意。取决于问题要求。 – David 2013-03-23 21:23:48

二进制搜索必须对此表做什么？ – SomeWittyUsername 2013-03-23 21:29:31

如果两个列表的长度都是n，那么您的建议方法是O（n^2）。更可能的是，这些列表可以有不同的长度，所以时间复杂度可以表示为O（mn）。

您可以将问题分成两个阶段： 1.订购唯一用它们的频率与Y元素 2.找到从这个名单，在X存在

的第一个项目作为这听起来像一个家庭作业问题我会让你考虑你能够以多快的速度完成这些单独的步骤。这些成本的总和会给你算法的总体成本。有许多方法比您目前拥有的两种列表长度的产品便宜。

来源

2013-03-23 21:19:16 sgmorrison

第一步：同时排序X和Y。假设它们的相应长度为m和n，该步骤的复杂度将是O(n log n) + O(m log m)。

第二步骤：计算每个X _我在ÿ和跟踪到目前为止最大计数。的X _我的排序Ÿ搜索是O(log n)。总第二步的复杂性：

总的复杂性：O(n log n) + O(m log m) + O(m log n)，或simpified：O(max(n,m) log n)

来源

2013-03-24 05:40:16

排序X和Y.然后做归并排序。每次遇到X中的相同元素时计算Y的频率。

因此，复杂度为O（nlogn）+ O（mlogm）+ O（m + n）= O（klogk）其中n，m = X，Y; k = max（m，n）

来源

2013-07-24 13:29:50 rnbcoder

什么是找到具有最高频率的数组中的元素最快的算法

回答

相关问题