在O（nlogn）时间内查找数组的模式

Question

我被要求在O（nlogn）中找到一个数组的模式。我可以在O（n）时间找到它，但不能想到另一种方式在O（nlogn）。我应该使用随机算法吗？ （我的O（n）解决方案是错误的）。我的O（n）解决方案类似于计数排序算法。

Answer 1

1. 对数组O的元素进行排序（n log n）
2. 迭代数组并计算相等相邻元素的数量。最高计数是模式。上）

所以它一起需要O（n log n）时间

Answer 2

http://bigocheatsheet.com/

通过那个方便的图表，您将看到：

• O（n）的性能优于O（n log n）
• 任何满足最坏情况O（n）的算法都满足最坏情况O（n log n）

我的猜测是，如果您的分析是正确的，那么您最初提出的问题并没有想到比您更好的最坏情况解决方案。