基于splice下标数组求解原数组元素移除顺序的优于O(N²)算法问题

问题描述 #

这是大型程序中的典型瓶颈模块：给定一组按执行顺序排列的splice操作下标数组，不需要实际执行所有splice操作（该方式时间复杂度为O(N²)），要求生成原数组各元素的移除顺序数组。

示例说明：
输入splice下标数组：[3, 1, 4, 4, 3, 1, 1]（下标为1开头，对应每次要删除的当前数组的位置）
原数组（1开头计数）：[a(1), b(2), c(3), d(4), e(5), f(6), g(7)]
执行逻辑：

1. 移除下标3的元素c，数组变为[a, b, d, e, f, g]
2. 移除下标1的元素a，数组变为[b, d, e, f, g]
3. 移除下标4的元素f，数组变为[b, d, e, g]
4. 移除下标4的元素g，数组变为[b, d, e]
5. 移除下标3的元素e，数组变为[b, d]
6. 移除下标1的元素b，数组变为[d]
7. 移除下标1的元素d，数组为空
   最终输出要求：数组第i位表示原数组第i个元素被移除的次序，示例输出为[2, 6, 1, 7, 5, 3, 4]（0开头索引，对应原数组a是第2次移除、b是第6次移除、c是第1次移除，以此类推）

需求背景（非核心逻辑，可选阅读） #

该需求来自seam carving（智能图像缩放）的实现场景，用于压缩seam的存储格式：由于每一步的seam只会左右偏移1px，因此可以存储为起始下标 + 逐位偏移标记的格式，长度为1024的seam仅需130字节即可存储。解压时需要把相对于当前数组的偏移下标转换为原数组的对应位置，也就是本问题的核心诉求。

最优解决方案（时间复杂度O(N log N)） #

核心思路：不需要真实修改数组元素的位置，只需要维护当前所有存活元素的计数，每次要删除当前数组的第k个元素时，等价于寻找原数组中「前缀存活元素数量等于k」的最小下标，该下标就是要删除的原数组位置。
我们可以用树状数组（Fenwick Tree）来高效维护存活元素的前缀和，支持单点更新和前缀和查询，配合二分查找即可快速定位到要删除的原下标。

具体实现步骤 #

1. 初始化长度等于原数组长度的计数数组，每个位置初始值为1，代表该位置元素存活
2. 用树状数组维护该计数数组的前缀和，支持两个核心操作：
   • 前缀和查询：查询到某个下标为止的存活元素总数量
   • 单点更新：将某个位置的计数减1，标记该元素已被移除
3. 遍历输入的splice下标数组，对每个下标k：
   • 用二分查找配合前缀和查询，找到前缀和等于k的最小原下标pos
   • 记录该原下标pos的移除次序为当前的操作步数
   • 调用单点更新接口，将pos位置的计数减1
4. 最终输出记录的移除次序数组即可

代码示例（JavaScript） #

// 树状数组实现
class FenwickTree {
  constructor(size) {
    this.n = size;
    this.tree = new Array(size + 1).fill(0);
    // 初始化所有位置为1（存活状态）
    for (let i = 1; i <= size; i++) {
      this.update(i, 1);
    }
  }

  // 单点更新：给idx位置加delta
  update(idx, delta) {
    while (idx <= this.n) {
      this.tree[idx] += delta;
      idx += idx & -idx;
    }
  }

  // 查询前缀和：1到idx位置的总和
  queryPrefix(idx) {
    let sum = 0;
    while (idx > 0) {
      sum += this.tree[idx];
      idx -= idx & -idx;
    }
    return sum;
  }

  // 查找第k个存活元素的原下标（1开头）
  findKthAlive(k) {
    let low = 1, high = this.n;
    while (low < high) {
      const mid = (low + high) >> 1;
      if (this.queryPrefix(mid) < k) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
}

// 主函数：传入原数组长度和splice下标数组（1开头）
function getRemoveOrder(originalLength, spliceIndices) {
  const ft = new FenwickTree(originalLength);
  // 结果数组，索引为原数组0开头下标，值为移除次序
  const result = new Array(originalLength);
  for (let step = 0; step < spliceIndices.length; step++) {
    const k = spliceIndices[step];
    const originalPos1 = ft.findKthAlive(k);
    const originalPos0 = originalPos1 - 1;
    // 移除次序为step+1（从1开始计数）
    result[originalPos0] = step + 1;
    ft.update(originalPos1, -1);
  }
  return result;
}

// 测试示例
console.log(getRemoveOrder(7, [3, 1, 4, 4, 3, 1, 1])); 
// 输出：[2, 6, 1, 7, 5, 3, 4]，完全匹配示例要求

复杂度说明 #

• 树状数组的单次更新和查询时间复杂度都是O(log N)
• 每次二分查找的时间复杂度是O(log N)
• 总共有N次操作，整体时间复杂度为O(N log N)，对比O(N²)的模拟splice方案，在N=1e4的场景下性能提升超过100倍，完全满足大型程序的性能要求。

内容的提问来源于stack exchange，提问作者Mark Kahn