基于索引数组生成目标顺序数组的快速算法与数据结构咨询

1. std::vector::erase的时间复杂度 #

不是O(1)。当调用erase删除vector中间位置的元素时，该位置后方的所有元素都需要向前移动一位填补空缺，单次erase的时间复杂度为O(k)，k是被删除位置后方的元素总数。你当前的朴素实现总时间复杂度为O(len²)，len稍大时性能损耗会非常明显。

2. 更优的算法实现方案 #

你要实现的功能本质是：维护一个动态有序元素集合，每次查询第k个现存元素，再将该元素从集合中删除。根据你的场景特征（调用量级为O(len!)，说明len必然很小，否则调用次数会高到无法正常运行），可以选两种优化方案：

• 如果len >= 20：使用线段树/树状数组（BIT）实现动态顺序统计
  实现逻辑：
  • 初始化长度为len+1的数组，每个位置存1，代表对应位置的数字存在
  • 每次输入idx[n]，查询前缀和等于idx[n]+1的位置，就是本次要取出的数值
  • 将该位置的值修改为0，代表元素已被删除
    单次查询和更新的时间复杂度都是O(log len)，单次调用getOrdering的总复杂度为O(len log len)，相比原实现提升极大。如果不想自己手动实现线段树，GCC环境下可以直接使用内置的__gnu_pbds::tree（策略基数据结构），直接调用find_by_order(k)就能获取第k个元素，删除操作也只需调用erase，接口非常简便。
• 如果len < 20：使用位掩码做极致优化
  实现逻辑：
  • 用一个整型变量mask的二进制位标记元素是否存在，初始值为(1 << (len + 1)) - 1
  • 每次借助CPU内置的POPCNT、CTZ等指令，快速找到第idx[n]个置位的位的位置，就是本次要取的数值
  • 直接将mask对应位清零即可
    这种方案所有操作都在CPU寄存器内完成，单次操作几乎是O(1)，是所有方案中性能最高的，完全适配你O(len!)调用量级的场景。

3. 关于O(1)操作的说明 #

不存在通用的、支持任意len的O(1)动态顺序统计+删除的数据结构。如果你的len始终很小（<=20），上面的位掩码方案已经可以达到近似O(1)的操作耗时，完全满足你的需求。

内容的提问来源于stack exchange，提问作者Floyd Everest