不修改原列表/集合、不保留排序结果，如何高效计算元素排名？

一、通用算法与数据结构方案（对应列表排名问题） #

预处理阶段 #

• 提取原列表所有元素，生成有序的唯一分数列表（通过排序后去重实现，时间复杂度O(N log N)）
• 统计每个分数的出现次数，再基于有序唯一列表计算前缀和映射表：记录每个分数对应的「小于该分数的元素总数」。比如原列表是[5,3,5,2,7]，有序唯一列表为[2,3,5,7]，次数统计是{2:1,3:1,5:2,7:1}，前缀和映射表就是{2:0,3:1,5:2,7:4}
• 存储这个前缀和映射表，无需保存完整排序列表

查询阶段 #

• 对于任意指定元素，直接从映射表中取出对应的前缀和，加1就是该元素的排名（排名从1开始，相同分数排名一致）。单次查询时间O(1)，E次查询总时间O(E)

复杂度说明 #

预处理时间O(N log N)，空间复杂度O(U)（U是唯一分数的数量，U≤N），在分数重复较多的场景下空间占用会远小于N，同时查询效率达到最优。

二、MongoDB专属解决方案（对应原始集合排名问题） #

针对千量级的MongoDB集合，以下几种方案效率都足够，可根据场景选择：

方案1：实时聚合统计单条文档排名 #

针对目标文档的score，直接统计集合中score大于该值的文档总数，加1就是排名。示例代码：

// 假设目标文档的_id为targetId
const targetScore = db.collection.findOne({ _id: targetId }).score;
const higherCount = db.collection.countDocuments({ score: { $gt: targetScore } });
const rank = higherCount + 1;

如果要批量处理E个文档，可循环执行上述逻辑，千量级数据下完全够用。

方案2：给score字段创建索引优化查询 #

给score字段创建降序单字段索引：

db.collection.createIndex({ score: -1 });

创建索引后，MongoDB执行$gt统计时会走索引扫描，速度比全表扫描快数倍，数据量越大优势越明显。

方案3：预计算排名字段（适合score更新不频繁的场景） #

如果score不是实时变动，可定期执行聚合任务，给每个文档计算并存储rank字段，后续查询直接读取该字段即可。示例聚合脚本：

db.collection.aggregate([
  // 按score降序排序
  { $sort: { score: -1 } },
  // 按score分组，统计同分数的文档数并收集文档_id
  { $group: { _id: "$score", docs: { $push: "$_id" }, count: { $sum: 1 } } },
  // 再次按score降序排序，保证窗口计算顺序正确
  { $sort: { _id: -1 } },
  // 计算累计文档数（到当前score为止的总文档数）
  { $setWindowFields: {
      sortBy: { _id: -1 },
      output: { cumulativeCount: { $sum: "$count", window: { documents: ["unbounded", "current"] } } }
    }
  },
  // 拆分分组的文档列表
  { $unwind: "$docs" },
  // 计算每个文档的排名（同分数排名一致）
  { $addFields: { rank: { $subtract: ["$cumulativeCount", { $subtract: ["$count", 1] }] } } },
  // 将计算结果合并回原集合
  { $merge: { into: "collection", on: "_id" } }
])

此方案查询效率最高（O(1)），适合score更新频率低的场景。

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