从长度为K的子数组中找到第L小/大的算法

Question

考虑一个值的数组{3,2,8,4,7,6,1}。我需要一种算法来查找每个长度为K的子数组中第L大/小的元素。

例如，对于上述数组，令K = 5，L = 3。我需要找到每个长度为K的子数组中的第三个最小值。

期望输出:

Subarray:
[3,2,8,4,7] = Third minimun is 4.
[2,8,4,7,6] = Third minimum is 6.
[8,4,7,6,1] = Third mininum is 6.

请帮我找到该算法。

- Raj

---

我最初考虑使用自平衡二叉搜索树，但是在查找其中的第L小/大元素时，时间复杂度会达到O(L)。因此，我们可以使用大小为k的窗口的最小堆和最大堆的组合，将前L-1个元素放入最小堆中，将前L-K个元素放入最大堆中。这样，获取第L小/大元素的时间复杂度将为O(1)。 - nice_dev

@vivek_23 通过在每个节点上增加以该节点为根的子树大小，将BST转换为顺序统计树。然后，在O(log k)中查找顺序统计信息。 - Dave

@Dave 是的，有道理。 - nice_dev

@vivek_23 当使用最小堆和最大堆时，何时将新元素添加到堆中，何时从堆中提取最小值和最大值。你能否分享一下伪代码给我？ - Raj

@Raj 在网上查找如何在整数流中找到运行中位数。你的问题看起来很相似。 - nice_dev

Answer 1

你可以在O(N log K)的时间内解决这个问题，其中N是数组的大小。

首先请注意，如果我们解决最小值的问题，那么最大值的解决方案也是相同的，只需将原始数组元素乘以-1即可。

因此，为了解决这个问题，我们需要一个支持添加、删除、查找集合中第k个项目的数据结构，然后我们可以使用滑动窗口循环所有需要的区间，根据需要添加和删除项目。

实际上，有许多结构可以在O(log N)的时间内支持所有这些操作，例如线段树、最小/最大堆、顺序统计树（一种B树）和其他一些结构。

顺序统计树是一种二叉搜索树，除了插入、查找和删除之外，还支持两个附加操作：

Select(i) - 查找树中存储的第i个最小元素。

Rank(x) - 查找元素x在树中的排名，即其在树的元素排序列表中的索引。

当自平衡树用作基本数据结构时，这两个操作都是O(log n)的。

示例代码（使用g++编译器的C++，该编译器幸运地在库中具有顺序统计树）

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

int main()
{
    int n,k,L;
    cin>>n>>k>>L;
    vector<int>A(n+1);
    for(int i=0; i<n; i++)cin>>A[i];
    ordered_set S;
    for(int i=0; i<k; i++)
        S.insert({A[i],i});

    for(int i=k; i<=n; i++)
    {
        cout<<S.find_by_order(L-1)->first<<" ";
        S.erase(S.find({A[i-k],i-k}));
        S.insert({A[i],i});
    }
}

- Photon

Answer 2

这里有一个更加轻便的解决方案，只使用C++的multisets。思路是维护两个multisets，第一个包含最小的L-1个数字，而另一个则包含其余数字。复杂度为O(N log K)。前K个插入和初始平衡需要O(K log K)时间。每次平衡操作将花费O(log K)时间，因为集合的不平衡值最多为1（绝对值）。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    int n, k, l;
    cin >> n >> k >> l;
    vector<int> a(n);
    for (int& x : a)
        cin >> x;
    multiset<int> small, large;

    auto balance = [&]() {
        while ((int)small.size() >= l) {
            large.insert(*--small.end());
            small.erase(--small.end());
        }

        while ((int)small.size() < l-1) {
            small.insert(*large.begin());
            large.erase(large.begin());
        }
    };

    auto add = [&](int x) {
        small.insert(x);
    };

    auto rem = [&](int x) {
        auto it = small.find(x);
        if (it != small.end())
            small.erase(it);
        else {
            it = large.find(x);
            large.erase(it);
        }
    };

    for (int i=0; i<k; i++)
        small.insert(a[i]);
    balance();
    for (int i=k; i<=n; i++) {
        cout << *large.begin() << '\n';
        if (i < n) {
            add(a[i]);
            rem(a[i-k]);
            balance();
        }
    }
}

- ivan100sic

Answer 3

一种实现方法是：

1. 将输入集合分成所需长度的子集合序列。
2. 从每个子集合中提取唯一元素
3. 对唯一元素的集合进行排序
4. 从排序后的集合中取第三个元素

在Clojure（Lisp变体）中，我们可以这样做：

(defn nth-least-by-l [c n l]
  (map #(list (nth (sort (set %)) (dec n)) %) (partition l 1 c)))

为您的测试集调用此函数：

(nth-least-by-l [3 2 8 4 7 6 1] 3 5)

返回

((4 (3 2 8 4 7)) (6 (2 8 4 7 6)) (6 (8 4 7 6 1)))

这段代码有点难以阅读。使用以下代码进行格式化

(do
  (println "Third minimums:")
  (doseq [[nval col] (nth-least-by-l [3 2 8 4 7 6 1] 3 5)]
    (println col " => " nval)))

生成以下输出：

(3 2 8 4 7)  =>  4
(2 8 4 7 6)  =>  6
(8 4 7 6 1)  =>  6

这是正确的。

- Bob Jarvis - Слава Україні