Hackerrank欺诈活动通知题代码优化:如何解决测试用例超时问题
超时问题核心原因
- 当前实现的单轮循环会对长度为d的窗口执行一次全量
sort操作,单次排序的时间复杂度为O(d log d),整体算法复杂度为O(n*d log d)。当测试用例达到题目给定的最大规模时,总计算量会突破1e9量级,远超C++单秒可处理约1e8次基础操作的常规速度阈值,必然触发时间限制。 - 原实现存在逻辑隐患:直接对传入的原数组执行排序操作,会打乱后续滑动窗口的元素顺序,样例通过属于巧合;额外对通知计数执行
notif-1的返回逻辑也属于无依据的错误修正,会导致计数偏差。
优化方案
- 利用题目给定的交易金额值域上限为200的约束,用长度为201的计数频率数组维护滑动窗口内的元素分布,完全规避排序操作。
- 初始时将前d个窗口元素的出现次数写入频率数组;后续每滑动一次窗口,仅需将窗口最左侧元素的计数减1、新加入窗口的右侧元素计数加1,单步操作复杂度为O(1)。
- 查找中位数时,直接遍历频率数组累计出现次数,定位到窗口长度对应的中位数位置即可,无需对窗口元素重新排序,单次中位数计算的复杂度仅为O(201)。
- 加入C++输入流加速配置,避免大规模测试用例下的输入耗时触发超时。
优化后的参考代码
#include <bits/stdc++.h> using namespace std; int activityNotifications(vector<int> expenditure, int d) { vector<int> cnt(201, 0); int notif = 0; // 初始化前d个元素的频率统计 for (int i = 0; i < d; i++) { cnt[expenditure[i]]++; } // 遍历所有需要检查的消费记录 for (int i = d; i < expenditure.size(); i++) { long double median; if (d % 2 == 1) { int target = d / 2 + 1; int sum = 0; for (int val = 0; val <= 200; val++) { sum += cnt[val]; if (sum >= target) { median = val; break; } } } else { int target1 = d / 2; int target2 = d / 2 + 1; int m1 = 0, m2 = 0, sum = 0; for (int val = 0; val <= 200; val++) { if (sum + cnt[val] < target1) { sum += cnt[val]; } else { m1 = val; break; } } sum = 0; for (int val = 0; val <= 200; val++) { if (sum + cnt[val] < target2) { sum += cnt[val]; } else { m2 = val; break; } } median = (m1 + m2) / 2.0; } if (expenditure[i] >= 2 * median) { notif++; } // 滑动窗口:移除最左侧元素,加入当前新元素 cnt[expenditure[i - d]]--; cnt[expenditure[i]]++; } return notif; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, d; cin >> n >> d; vector<int> expenditure(n); for (int i = 0; i < n; i++) { cin >> expenditure[i]; } cout << activityNotifications(expenditure, d) << endl; return 0; }
内容的提问来源于stack exchange,提问作者Philona Reetha Sebastian
相关产品推荐
相关产品推荐

