3709. 设计考试成绩追踪器

Medium

题目描述

Alice 经常参加考试，她想要追踪自己的成绩并计算特定时间段内的总分。

实现 ExamTracker 类：

ExamTracker(): 初始化 ExamTracker 对象。
void record(int time, int score): Alice 在时间 time 参加新考试并获得分数 score。
long long totalScore(int startTime, int endTime): 返回 Alice 在时间 startTime 和 endTime（包含）之间参加的所有考试的总分。如果在指定时间区间内没有记录的考试，则返回 0。

保证函数调用按时间顺序进行。即：

对 record() 的调用时间严格递增。
Alice 永远不会询问需要未来信息的总分。即如果最新的 record() 调用时间为 t，那么 totalScore() 总是以 startTime <= endTime <= t 的方式调用。

示例 1：

输入：
["ExamTracker", "record", "totalScore", "record", "totalScore", "totalScore", "totalScore", "totalScore"]
[[], [1, 98], [1, 1], [5, 99], [1, 3], [1, 5], [3, 4], [2, 5]]

输出：
[null, null, 98, null, 98, 197, 0, 99]

解释：
ExamTracker examTracker = new ExamTracker();
examTracker.record(1, 98); // Alice 在时间 1 参加考试，得分 98
examTracker.totalScore(1, 1); // 时间 1 到 1 之间，Alice 在时间 1 参加了 1 次考试，得分 98，总分为 98
examTracker.record(5, 99); // Alice 在时间 5 参加考试，得分 99
examTracker.totalScore(1, 3); // 时间 1 到 3 之间，Alice 在时间 1 参加了 1 次考试，得分 98，总分为 98
examTracker.totalScore(1, 5); // 时间 1 到 5 之间，Alice 在时间 1 和 5 参加了 2 次考试，得分 98 和 99，总分为 197
examTracker.totalScore(3, 4); // Alice 在时间 3 到 4 之间没有参加考试，因此答案是 0
examTracker.totalScore(2, 5); // 时间 2 到 5 之间，Alice 在时间 5 参加了 1 次考试，得分 99，总分为 99

约束条件：

1 <= time <= 10^9
1 <= score <= 10^9
1 <= startTime <= endTime <= t，其中 t 是最近一次 record() 调用的时间值
record() 调用的时间严格递增
在 ExamTracker() 之后，第一个函数调用总是 record()
总共最多进行 10^5 次 record() 和 totalScore() 调用

解题思路

这道题要求我们设计一个数据结构来追踪考试成绩并快速查询时间区间内的总分。

核心思路：

由于时间是严格递增的，我们可以维护两个数组：

times 数组：存储每次考试的时间
prefix 数组：存储前缀和，prefix[i] 表示前 i+1 次考试的总分

查询优化：

对于区间查询，我们需要找到时间区间 [startTime, endTime] 对应的考试索引范围。由于时间有序，可以使用二分查找：

使用 lower_bound 找到第一个 >= startTime 的位置
使用 upper_bound 找到第一个 > endTime 的位置

具体步骤：

record(time, score): 将时间添加到 times 数组，将累计总分添加到 prefix 数组
totalScore(startTime, endTime):
- 二分查找找到左右边界索引
- 如果区间无效则返回 0
- 否则使用前缀和计算区间总分

这种方法的优势是查询时间复杂度为 O(log n)，非常适合频繁查询的场景。

代码实现

class ExamTracker {
private:
    vector<int> times;
    vector<long long> prefix;
    
public:
    ExamTracker() {
        
    }
    
    void record(int time, int score) {
        times.push_back(time);
        long long totalSoFar = prefix.empty() ? 0 : prefix.back();
        prefix.push_back(totalSoFar + score);
    }
    
    long long totalScore(int startTime, int endTime) {
        int left = lower_bound(times.begin(), times.end(), startTime) - times.begin();
        int right = upper_bound(times.begin(), times.end(), endTime) - times.begin() - 1;
        
        if (left > right) {
            return 0;
        }
        
        long long rightSum = prefix[right];
        long long leftSum = left > 0 ? prefix[left - 1] : 0;
        return rightSum - leftSum;
    }
};

class ExamTracker:

    def __init__(self):
        self.times = []
        self.prefix = []

    def record(self, time: int, score: int) -> None:
        self.times.append(time)
        total_so_far = self.prefix[-1] if self.prefix else 0
        self.prefix.append(total_so_far + score)

    def totalScore(self, startTime: int, endTime: int) -> int:
        import bisect
        left = bisect.bisect_left(self.times, startTime)
        right = bisect.bisect_right(self.times, endTime) - 1
        
        if left > right:
            return 0
        
        right_sum = self.prefix[right]
        left_sum = self.prefix[left - 1] if left > 0 else 0
        return right_sum - left_sum

public class ExamTracker {
    private List<int> times;
    private List<long> prefix;

    public ExamTracker() {
        times = new List<int>();
        prefix = new List<long>();
    }
    
    public void Record(int time, int score) {
        times.Add(time);
        long totalSoFar = prefix.Count > 0 ? prefix[prefix.Count - 1] : 0;
        prefix.Add(totalSoFar + score);
    }
    
    public long TotalScore(int startTime, int endTime) {
        int left = BinarySearchLeft(startTime);
        int right = BinarySearchRight(endTime) - 1;
        
        if (left > right) {
            return 0;
        }
        
        long rightSum = prefix[right];
        long leftSum = left > 0 ? prefix[left - 1] : 0;
        return rightSum - leftSum;
    }
    
    private int BinarySearchLeft(int target) {
        int left = 0, right = times.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (times[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    private int BinarySearchRight(int target) {
        int left = 0, right = times.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (times[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var ExamTracker = function() {
    this.times = [];
    this.prefix = [];
};

ExamTracker.prototype.record = function(time, score) {
    this.times.push(time);
    const totalSoFar = this.prefix.length > 0 ? this.prefix[this.prefix.length - 1] : 0;
    this.prefix.push(totalSoFar + score);
};

ExamTracker.prototype.totalScore = function(startTime, endTime) {
    const left = this.binarySearchLeft(startTime);
    const right = this.binarySearchRight(endTime) - 1;
    
    if (left > right) {
        return 0;
    }
    
    const rightSum = this.prefix[right];
    const leftSum = left > 0 ? this.prefix[left - 1] : 0;
    return rightSum - leftSum;
};

ExamTracker.prototype.binarySearchLeft = function(target) {
    let left = 0, right = this.times.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (this.times[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

ExamTracker.prototype.binarySearchRight = function(target) {
    let left = 0, right = this.times.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (this.times[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
record	O(1)	O(1)
totalScore	O(log n)	O(1)
总体	O(n + m log n)	O(n)

其中 n 是 record 调用次数，m 是 totalScore 调用次数。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析