如何找到k大小的所有子数组的第n个最小/最大值(滑动窗口问题)
如何找到k大小的所有子数组的第n个最小/最大值(滑动窗口问题)
提问于 2019-03-10 13:39:37
对于大小为k的所有子数组，有那么多的引用来查找最小/最大值，但是如何以最好的方式找到第n个最大/最小值。如果我们只需要找到子阵列的最小/最大值，那么我们就可以使用线性时间复杂度的deque解。但是对于第9分钟/最大，我无法找到解决办法。
注: n<=k
示例: arr = {7,1,4,20,11,17,15} n=2，k=4
产出:4 4 11 15
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-03-11 16:00:27
我相信您需要的数据结构是一个修改过的二进制搜索树(BST)，其中每个节点还存储它的子树的大小。
在BST中添加、删除元素或寻找n元素，然后全部变成log(K)*。因此，在将窗口滑动到数组上时，您有3个log(K)操作，假设给定数组中的总N元素，因此总的时间复杂度是N*log(K)。
- 您需要一个平衡的BST (例如，红色黑树)来保持这个时间的复杂性。如果您来自Codeforce或Hackerrank这样的在线评审员，请记住他们经常提供会生成退化BSTs的输入。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55088264
复制相关文章
相似问题
腾讯云开发者
