1

我们可以使用O(n)时间复杂度的Median of Medians 算法轻松找到第 n 个最大的。 如果我们必须在同一个数组中多次找到第 n 个最大的数，最好的方法是对O(NlogN)进行排序 ，然后在O(1)时间复杂度中找到该数。 但是，当数组大小增加并且我们必须找到第 n 个最大的数，比如 array.length/3 th 最大或 array.length/2 th 最大 时，什么是有效的算法。例子



Array- 1,3,2,4,5 n=2 Answer-4   
New Array 1,3,2,4,5,7  n=2 answer-5  
New Array 1,3,2,4,5,7,3 n=2 answer-5

注意
n 取决于数组的长度。
请帮帮我。

4

2 回答 2

7

我确信您必须始终跟踪整个阵列。假设我们收到 100, 99, 98, ..., 1, 0, -1, ... 那么第 n 个最大的数字将遵循相同的顺序，尽管速度变慢：100、100、99、99、98、 98...

本质上，我们不能忘记输入中的任何数字，因为在这种情况下，每个数字最终都会被选为第 n 个最大的数字。

也就是说，每次我们读入一个新元素时，都有一个 O(log N) 算法（对于 N，整体元素的数量）来“更新”第 n 个最大的元素，这似乎可能是最优的。或多或少，只需保留 n 个最大元素的最小优先级队列和 Nn 个较小元素的最大优先级队列。每当 n 增加（例如，array.length / 3 增加）时，将一些东西从较小元素队列中拉出到较大元素队列中；每次我们读取一个新元素时，将其放入适当的队列中，可能会将一个元素从“较大元素”队列中撞到“较小元素”队列中。

于 2012-07-09T10:24:37.830 回答
0

有趣的问题。这取决于有多少值是唯一的，以及您从新数组开始、搜索和插入的频率。

对于许多 n 是唯一的，很少从频繁插入/搜索的新数组开始，我的第一个预感是：

  • 创建一个 max-heaptip和一个 max-heap bulk，让 n 成为你想要的排名（第 n 个值）
  • 插入：将新节点推入tip；如果tip.size() >= (n-1)，弹出tip.top()并推入bulk
  • 查询词语：返回bulk.top()

这应该为您O(N log(N))提供启动、O(log(N))插入（比排序快得多）和O(1)搜索。

如果唯一值的数量远小于 N，我可能会使用计数排序，然后按值对 bin 进行排序。

编辑：更详细地查看 Louis Wasserman 的答案，它似乎与我的第一个算法几乎完全重叠。但是，仍然想建议不要将“从较小元素队列中取出的东西”拉出来，而是可以通过选择最大元素作为推入最小堆的元素来进行搜索 O(1)。

于 2012-07-09T19:15:00.907 回答