HackerRank爬取排行榜问题Runtime Error排查与修复求助

我来帮你排查下问题所在哈～你的代码在小测试用例里能跑通，但遇到HackerRank里的大数据测试用例（TestCase6-9）就触发Runtime Error，核心原因是时间复杂度太高，导致超时。

问题出在哪？ #

你的代码逻辑是每次把Alice的当前分数和整个原分数组合并，再重新排序生成排行榜，然后遍历计算排名：

• 每次合并排序的操作时间复杂度是O((N+M)log(N+M))，其中N是原分数的数量，M是Alice的分数数量。如果N和M都达到10^5级别，重复M次这样的操作后，总时间复杂度会飙升到O(M*(N+M)log(N+M))，完全超出了题目允许的时间限制。
• 后续用count和字典生成排名的逻辑也绕了弯路，进一步增加了不必要的计算开销。

修复方案：预处理+二分查找 #

我们可以通过预处理原排行榜和二分查找来把时间复杂度降到可接受的范围：

步骤1：预处理原排行榜

先把原分数数组去重并保持降序排列，得到一个没有重复值的有序列表。比如原分数是[100, 100, 50, 40, 40, 20, 10]，处理后会变成[100, 50, 40, 20, 10]，每个元素对应的排名就是它的索引+1。

步骤2：用二分查找快速定位Alice的排名

对于Alice的每个分数，我们用二分查找在预处理后的有序列表里快速找到它的位置，直接计算出排名：

• 如果分数大于等于列表中的某个元素，排名就是该元素的索引+1；
• 如果分数小于所有元素，排名就是列表长度+1。

优化后的代码 #

import bisect

# 读取输入
scores_count = int(input())
scores = list(map(int, input().rstrip().split()))
alice_count = int(input())
alice = list(map(int, input().rstrip().split()))

# 预处理：去重并保持降序（遍历去重比set更高效，适配原scores可能已降序的场景）
unique_scores = []
prev_score = None
for s in scores:
    if s != prev_score:
        unique_scores.append(s)
        prev_score = s

# 处理Alice的每个分数
for score in alice:
    # bisect_right在降序列表中找到第一个小于当前分数的位置
    rank_idx = bisect.bisect_right(unique_scores, score)
    print(rank_idx + 1)

为什么这个方案能解决问题？ #

• 预处理去重的时间复杂度是O(N)（如果原分数已经是降序的话），就算用set再排序也只是O(NlogN)，远低于原来的重复排序开销；
• 每个Alice的分数用二分查找的时间复杂度是O(logK)（K是去重后的分数数量），总时间复杂度降到O(N + MlogK)，完全能处理大数据量的测试用例。

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