在阵列中找到频率最高的元素的最快算法是什么

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或等同于您的语言.

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