6

我有两个输入数组 X 和 Y。我想返回数组 X 中在数组 Y 中出现频率最高的那个元素。

这样做的简单方法要求对于数组 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) 或更快的时间内做到这一点吗？

4

8 回答 8

7

使用哈希表将键映射到计数。对于数组中的每个元素，做喜欢counts[element] = counts[element] + 1或你的语言的等价物。

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

于 2013-03-23T21:16:34.227 回答
3

或者，如果您可以有其他数据结构，您可以遍历数组 Y，每个数字在哈希表中更新其频率。这需要O(N(Y)时间。然后走 X 找出 X 中哪个元素的频率最高。这需要O(N(X))时间。总体：线性时间，因为您必须至少查看两者X以及任何实现中的每个元素（编辑：严格来说，这在所有情况/所有实现中都不是正确的，正如jwpat7指出的那样，尽管在最坏的情况下它是正确的案例），你不能比这更快。Y

于 2013-03-23T21:16:38.103 回答
2

常用算法的时间复杂度如下：

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（非常可靠）来查找数组中频率最高的元素。

注意：这是假设您要使用排序算法。否则，如果您被允许使用任何数据结构，我将使用具有恒定查找时间的 hashmap/hashtable 类型结构。这样，您只需匹配键并更新频率键值对。希望这可以帮助。

于 2013-03-23T21:17:37.013 回答
2

第一步：对X和Y进行排序。假设它们对应的长度是m和n，这一步的复杂度将是 O(n log n) + O(m log m)。

第二步：计算Y 中的每个X i并跟踪迄今为止的最大计数。在已排序的Y中搜索X i是。第二步的总复杂度为：O(log n)O(m log n)

总复杂度：O(n log n) + O(m log m) + O(m log n)，或简化：O(max(n,m) log n)

于 2013-03-24T05:40:16.880 回答
1

基于分而治之概念的合并排序为您提供 O(nlogn) 复杂度

于 2013-03-23T21:13:55.987 回答
1

如果两个列表的长度均为 n，您建议的方法将是 O(n^2)。更有可能的是列表可以是不同的长度，因此时间复杂度可以表示为 O(mn)。

您可以将您的问题分为两个阶段： 1. 按频率对 Y 中的唯一元素进行排序 2. 查找此列表中存在于 X 中的第一项

因为这听起来像是一个家庭作业问题，所以我会让你想想你可以多快完成这些单独的步骤。这些成本的总和将为您提供算法的总体成本。有许多方法会比您当前拥有的两个列表长度的乘积便宜。

于 2013-03-23T21:19:16.727 回答
1

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

所以复杂度，O(nlogn) + O(mlogm) + O(m+n) = O(klogk) 其中 n,m = X, Y 的长度；k = 最大值(m,n)

于 2013-07-24T13:29:50.710 回答
0

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

于 2013-03-23T21:13:08.760 回答