当数组大小增加时，找到第n个最大数目(多次) [英] Finding nth largest number (many times) when the array size is increasing

问题描述

我们可以使用 O(n)时间复杂度的 中位数算法中位数 轻松找到第n大.
如果我们必须多次查找同一数组中第n个最大的数字，那么最好是对 O(NlogN)进行排序，然后在 O(1)时间中找到数字复杂性.
但是，当数组大小增加并且
我们必须找到第n大数字，例如array.length/3大或array.length/2大.
示例

We can easily find the nth largest using the Median of Medians Algorithm in O(n) time complexity.
If we have to find multiple times the nth largest numbers in the same array the best would be to sort O(NlogN) and then find the number in O(1) time complexity.
But what will be the efficient algorithm when the array size is increasing and
we have to find the nth largest number say array.length/3 th largest or array.length/2 th largest.
Example

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取决于数组的长度.
请帮帮我.

Note
n depends upon length of the array.
Please do help me.

推荐答案

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

I'm convinced that you have to keep track of the entire array at all times. Suppose that we receive 100, 99, 98, ..., 1, 0, -1, ... Then the nth-largest number will follow the same sequence, albeit slowed down: 100, 100, 99, 99, 98, 98...

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

Essentially, we can't forget any numbers from the input, because in this scenario each number will eventually be chosen as the nth largest.

也就是说，有一个O(log N)算法(对于N，总元素数)，每次读取一个新元素时更新"第n个最大元素，这似乎是最佳的.或多或少，只保留n个最大元素的最小优先级队列，和n-n个较小元素的最大优先级队列.每当n增加时(例如array.length/3增加)，就将某些内容从较小元素队列中拉出到较大元素队列中；每次我们读取一个新元素时，将其放入适当的队列中，有可能将一个元素从较大元素"队列中撞到较小元素"队列中.

That said, there's an O(log N) algorithm (for N, the number of elements overall) to "update" the nth largest element each time we read in a new element, which seems probably optimal. More or less, just keep a min priority queue of the n largest elements, and a max priority queue of the N-n smaller elements. Whenever n increases (array.length / 3 increases, for example), pull something out of the smaller-elements queue into the larger-elements queue; every time we read a new element, put it into the appropriate queue, possibly bumping an element out of the "larger-elements" queue into the "smaller-elements" queue.

这篇关于当数组大小增加时，找到第n个最大数目(多次)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！