HackerRank欺诈活动通知题Python代码超时优化咨询

• 核心问题是时间复杂度过高：你当前的实现每次计算中位数都要对长度为d的窗口切片做全量排序，单次排序耗时O(d log d)，外层循环总共有n-d次迭代，整体时间复杂度为O(n*d log d)。当测试用例的n和d达到10^5量级时，运算量会远超过时间限制阈值。
• 额外开销：每次生成窗口切片expenditure[i:d+i]都会创建新的列表，产生O(d)的内存拷贝开销，进一步降低运行效率。

本题隐含约束为单日消费额最大值不超过200，因此可以采用计数数组+滑动窗口的方案将时间复杂度降到O(n)，完全满足大数据量测试要求：

1. 维护一个长度为201的计数数组，记录当前滑动窗口内每个消费额的出现次数
2. 窗口滑动时仅需更新计数数组：移出窗口的旧值计数减1，新加入窗口的值计数加1，单次更新耗时O(1)
3. 计算中位数时直接遍历计数数组累加次数，找到对应中间位置的数值即可，单次查找最多遍历201个元素，耗时O(1)

优化后的实现代码如下：

n, d = map(int, input().split())
expenditure = list(map(int, input().split()))
count = 0
# 消费额最大为200，初始化计数数组
freq = [0] * 201
# 初始化第一个窗口的计数
for i in range(d):
    freq[expenditure[i]] += 1

def get_double_median():
    # 直接返回中位数的2倍，避免浮点运算
    cum = 0
    if d % 2 == 1:
        mid = d // 2 + 1
        for num in range(201):
            cum += freq[num]
            if cum >= mid:
                return num * 2
    else:
        mid1, mid2 = d//2, d//2 + 1
        m1 = m2 = 0
        for num in range(201):
            cum += freq[num]
            if not m1 and cum >= mid1:
                m1 = num
            if cum >= mid2:
                m2 = num
                break
        return m1 + m2

for i in range(d, n):
    current = expenditure[i]
    if current >= get_double_median():
        count +=1
    # 滑动窗口更新计数
    freq[expenditure[i-d]] -= 1
    freq[current] += 1

print(count)

用你给出的小型测试用例运行上述优化代码，得到的输出结果为2，符合预期。

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