c++ - 处理索引不断变化的数组的数据结构

Question

我有一个数组，其中包含 8 个元素的空间。我想在以下数组指示的索引处用数字 8,7,...,1 填充此数组:

7 4 4 2 1 2 0 0

您一定注意到某些索引在重复。这是因为这些数字表示剩余数组的索引。

我将指导您完成数组填充的步骤，这样您就明白了:

初始数组(带有索引)

_ _ _ _ _ _ _ _
0 1 2 3 4 5 6 7

第一步

_ _ _ _ _ _ _ 8
0 1 2 3 4 5 6 -

第 2 步

_ _ _ _ 7 _ _ 8
0 1 2 3 - 4 5 -

请注意在我填写“7”时索引是如何更新的，这样我也可以在索引 4 处填写“6”，因为索引 4 是一个新位置。

第 3 步

_ _ _ _ 7 6 _ 8
0 1 2 3 - - 4 -

第四步

_ _ 5 _ 7 6 _ 8
0 1 - 2 - - 3 -

第 5 步

_ 4 5 _ 7 6 _ 8
0 - - 1 - - 2 -

第 6 步

_ 4 5 _ 7 6 3 8
0 - - 1 - - - -

第七步

2 4 5 _ 7 6 3 8
- - - 0 - - - -

最后的地方可以填“1”。

如果我必须在索引 i 处填充，我已经解决了直接扫描数组寻找第 i 个空位的问题。它是 O(n^2)。我需要更好的。

问题:是否有数据结构可以优化上述算法？还是算法本身可以改进？

注意:我曾尝试使用 BIT，但失败了。

Answer 1

将所有初始索引存储在二叉搜索树中。还与每个节点一起存储子节点总数(所有更深层次)。

在数组中插入一个元素后，立即从 O(log n) 的树中删除它的索引。同时更新 child 的数量。

要在“新索引”中索引 i 处的数组中进行下一次插入，您需要按照搜索树的顺序找到第 i 个元素，这将为您提供“原始”索引中的位置。由于可以查询每个节点的 child 数量，因此也可以在 O(log n) 中完成。

因此，完整的平均和最坏情况复杂度为 O(n log n)。