这道题的正解是 树状数组,但是我们用朴素解法 二重循环枚举 也能在考试时拿到一定的分数。
题意:给定数组 record 和阈值 threshold,统计满足 i<j 且 record[i]−record[j]>threshold 的下标对个数(严重性能逆序对)。
朴素做法:两重循环枚举所有 0≤i<j<n,若 record[i]−record[j]>threshold,答案加 1。
小数据可以过;当 n 达到 105 时,O(n2) 会超时,需要后面的树状数组做法。
在一家快速发展的互联网公司里,系统工程师小李正在开发一款高效的日志分析工具,旨在帮助运维团队更好地理解和优化语音合成系统的运行状况。为了提高工具的洞察力,他需要解决一个关键问题:如何通过分析一段时间内的合成请求的实时率 RTF (合成耗时 /目标文本的音频时长)记录来识别“性能逆序对”的总数,实时率越高代表性能越差。
在这个系统中,“性能逆序对”被定义为一种情况,即如果某次请求的实时率比之后某次请求的实时率大,则这两者构成一个“性能逆序对”。这可以帮助运维团队识别出系统的性能退化点或者异常波动,从而采取措施优化系统性能。
具体来说,给定一个数组 record ,它代表了一段时间内每次请求的实时率* 100 (按时间顺序排列,因正常场景实时率 <1 ,因此对数值进行放大 100 并取整)。小李的任务是设计并实现一个程序,该程序能够计算并返回这段时间内存在的“性能逆序对"总数。每个“性能逆序对”由两个索引 i 和 j 组成,满足条件 0<=i<j<record.length 并且 record[i]>record[j] 。如果 record[i]−record[j]>threshold ,则该性能逆序对称为"严重性能逆序对"。
请协助小李完成这个功能的开发,确保它能高效地处理大量的日志数据,并提供即时反馈。具体任务包括编写一个函数,输入是一个整数数组 record,输出是其中存在的“严重性能逆序对”的总数。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册