如何高效比较三维点组成的二维数组以删除被支配行？

你需要解决的是经典的三维天际线（Skyline）查询问题：给定一组三维坐标点，删除所有被其他点支配的点（支配规则为：点A的各坐标均≤点B的对应坐标，且至少一个坐标严格小于，此时B需被剔除）。

现有实现的问题 #

你当前的O(n³)嵌套循环实现存在两个核心问题：

• 时间复杂度极高，当点数量达到数千级时，计算耗时会快速膨胀。
• 逻辑漏洞：仅判断“所有坐标≤”的条件，未校验“至少一个严格小于”的要求，会误删与自身完全相等的点（如示例中第1个和第9个重复点，按规则不应删除）。

O(n log n) 高效实现方案 #

核心思路 #

通过排序降维将三维问题转化为二维动态查询，避免无意义的全点对比较：

• 排序降维：先对所有点按x坐标升序排序，x值相等时按y升序排列，y值也相等时按z升序排列。排序后，对于任意点P，只有排在它前面的点（x≤P.x）才有可能支配P，排在后面的点x值更大，不可能满足x≤P.x的支配条件，无需纳入比较范围。
• 问题转化：排序完成后，判断点P是否被支配等价于：在已经处理过的点中，是否存在y' ≤ P.y 且 z' ≤ P.z 的点。若存在则P被删除，否则保留。
• 数据结构优化：上述“查询所有y' ≤ Y的点中最小z值”的操作，可以通过坐标压缩+树状数组实现，将单次查询/更新的时间复杂度降到O(log n)。

具体实现步骤 #

1. 预处理
   • 对原始点集去重，完全相等的点不会互相支配，仅保留一个即可减少无效计算。
   • 收集所有点的y坐标，排序去重后做坐标压缩，将浮点数y映射为连续的整数排名，适配树状数组的索引要求。
2. 排序点集：按x升序、y升序、z升序排列所有点。
3. 初始化树状数组：每个位置的初始值设为无穷大（大于所有可能的z值），用于维护对应y排名下的最小z值。
4. 遍历处理每个点
   • 根据当前点P的y值对应的排名，查询树状数组中前缀到该排名的最小z值min_z。
   • 若min_z ≤ P.z：说明存在已处理的点满足x'≤P.x、y'≤P.y、z'≤P.z，即P被支配，直接跳过。
   • 若min_z > P.z：说明P不被任何已处理的点支配，保留该点。更新树状数组中P.y对应排名的位置，将值设为当前值和P.z的较小值。

示例验证 #

用你提供的点集按上述步骤处理后，被删除的点正好是你提到的第4、7、8个点，完全匹配规则要求。

复杂度分析 #

• 点集排序耗时O(n log n)，y坐标压缩耗时O(n log n)，遍历过程中每个点仅需一次查询和一次更新（每次O(log n)），总时间复杂度为O(n log n)，相比原O(n³)实现效率提升显著。

注意事项 #

• 树状数组需支持前缀最小值查询，初始化时的无穷大值要大于所有可能的z坐标范围。
• 如果需要保留所有重复点，仅需在判断min_z ≤ P.z时，额外校验对应点与P是否完全相等，若相等则不判定为支配即可。

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