You need to enable JavaScript to run this app. Hackerrank欺诈活动通知题代码优化:如何解决测试用例超时问题
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.30 01:06:03