algorithm - 在数组中找到频率最高的元素的最快算法是什么

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 或您的语言的等效项。

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