arrays - 有效插入数组后查找每个元素的下限和上限

Question

假设数组有元素[1,n]。一个接一个地连续输入元素(m个查询)。如下所示。

1. 5 所以你必须将 1 打印为 floor，将 10 打印为 ceil 然后数组变为 [1,5,10]
2. 2 所以将 1 打印为 floor，将 5 打印为 ceil，数组变为 [1,2,5,10]

像这样给出m个查询。在我们维护 arraylist 排序时，floor 和 ceil 可以用 O(log n) 时间复杂度找到。

但问题是找到插入的元素位置是 O(log n) 并且插入是 O(n) 在最坏的情况下移动其他数字导致 O(log n) + O(n) 每个查询。

因此对于 m 个查询，在最坏的情况下它将是 mxO(logn + n)，这太昂贵了。我希望此操作的执行效率低于 mxO(logn + n)。

Answer 1

您应该使用平衡二叉搜索树而不是数组。插入和下限/上限(即“floor”和“ceil”)都在 O(log n) 中完成，总运行时间为 O(m log m).

您没有提到语言，但作为示例，使用 C++ set 容器(实现二叉搜索树)代码如下所示:

std::set<int> A;
A.insert(1);
A.insert(n);

for(int i = 0; i < m; ++i) {
    int x;
    scanf("%d", &x);
    assert(1 < x && x < n);
    auto iter = A.insert(x).first;
    printf("floor: %d, ceil: %d\n", *prev(iter), *next(iter));
}