查找数组中出现频率最高的元素的最快算法是什么

Question

我有两个输入数组 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) 或更快的时间内完成此操作吗？

Answer 1

使用哈希表将键映射到计数。对于数组中的每个元素，请执行

counts[element] = counts[element] + 1

或您语言的等效操作。

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

Answer 2

或者，如果您可以拥有其他数据结构，则可以遍历数组 Y，为每个数字更新其在哈希表中的频率。这需要

O(N(Y)

时间。然后遍历 X 找出 X 中出现频率最高的元素。这需要

O(N(X))

时间。总体而言：线性时间，并且因为您必须在任何实现中至少查看

X

和

Y

的每个元素（编辑：严格来说，这在所有情况/所有实现中都不是正确的，如 jwpat7 指出，尽管在最坏的情况下确实如此），但你不能比这更快了。

Answer 3

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

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)  

一般来说，当遍历列表来满足特定条件时，你真的无法比线性时间做得更好。如果您需要对数组进行排序，我会说坚持使用合并排序（非常可靠）来查找数组中出现频率最高的元素。

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

Answer 4

第一步：对 X 和 Y 进行排序。假设它们对应的长度为m和n，则此步骤的复杂度将为

O(n log n) + O(m log m)

。

第二步：计算 Y 中的每个 _Xi 并跟踪迄今为止的最大计数。在已排序的 Y 中搜索 _Xi 是

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)

Answer 5

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

Answer 6

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

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

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

Answer 7

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

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

Answer 8

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

Answer 9

如果想从数组中查找最高频率，您可以这样编码，该代码是用 JavaScript 编写的，但也可以在任何其他语言中使用此方法。

 // Declare an array
     let array =[1,2,3,4,5,3,3,2,2,3,3,3,3,1,1,1,4]
     //create empty object
     let obj={}
     for (let index = 0; index < array.length; index++) {
      const element = array[index];
    obj[array[index]] = obj[array[index]]? obj[array[index]]+1 :1 ;
    }
    //object with frequency of each element
     //   {1: 4,2: 3,3: 7,4: 2,5: 1} 
    console.log(obj)
    let high=Object.keys(obj)[0]
    for(let key in obj){
    if(obj[high] < obj[key]){
    high =key
    }
    }
    console.log(high) //3