漳州建网站,前十名少儿编程机构,python基础教程第二版课后答案,网站建设找客户渠道题目#xff1a;
有 n 个 (id, value) 对#xff0c;其中 id 是 1 到 n 之间的一个整数#xff0c;value 是一个字符串。不存在 id 相同的两个 (id, value) 对。
设计一个流#xff0c;以 任意 顺序获取 n 个 (id, value) 对#xff0c;并在多次调用时 按 id 递增的顺序…题目
有 n 个 (id, value) 对其中 id 是 1 到 n 之间的一个整数value 是一个字符串。不存在 id 相同的两个 (id, value) 对。
设计一个流以 任意 顺序获取 n 个 (id, value) 对并在多次调用时 按 id 递增的顺序 返回一些值。
实现 OrderedStream 类
OrderedStream(int n) 构造一个能接收 n 个值的流并将当前指针 ptr 设为 1 。String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后 如果流存储有 id ptr 的 (id, value) 对则找出从 id ptr 开始的 最长 id 连续递增序列 并 按顺序 返回与这些 id 关联的值的列表。然后将 ptr 更新为最后那个 id 1 。 否则返回一个空列表。 示例 输入
[OrderedStream, insert, insert, insert, insert, insert]
[[5], [3, ccccc], [1, aaaaa], [2, bbbbb], [5, eeeee], [4, ddddd]]
输出
[null, [], [aaaaa], [bbbbb, ccccc], [], [ddddd, eeeee]]解释
OrderedStream os new OrderedStream(5);
os.insert(3, ccccc); // 插入 (3, ccccc)返回 []
os.insert(1, aaaaa); // 插入 (1, aaaaa)返回 [aaaaa]
os.insert(2, bbbbb); // 插入 (2, bbbbb)返回 [bbbbb, ccccc]
os.insert(5, eeeee); // 插入 (5, eeeee)返回 []
os.insert(4, ddddd); // 插入 (4, ddddd)返回 [ddddd, eeeee]提示
1 n 10001 id nvalue.length 5value 仅由小写字母组成每次调用 insert 都会使用一个唯一的 id恰好调用 n 次 insert
解法基于数组和指针的流式处理
解题思路
我们需要设计一个数据结构能够按 id 递增的顺序返回 (id, value) 对的值。由于 id 是唯一的且范围固定1 到 n我们可以使用一个数组来存储这些值并通过一个指针 ptr 来跟踪当前可以返回的最小 id。
具体步骤如下 初始化 使用一个大小为 n 1 的数组 stream 来存储 (id, value) 对。数组的索引直接对应 id方便快速访问。 初始化指针 ptr 为 1表示下一个需要返回的 id 是 1。 插入操作 将 (idKey, value) 对存储到数组 stream 的 idKey 位置。 检查当前指针 ptr 是否指向一个已经存储了值的 id。如果是则从 ptr 开始依次检查连续的 id 是否已经存储并将对应的 value 加入结果列表。 更新指针 ptr 为最后一个连续 id 的下一个位置。 返回结果列表。
代码实现
class OrderedStream {
private:vectorstring stream; // 用于存储 (id, value) 对的数组int ptr; // 当前指针指向下一个应该返回的 idpublic:OrderedStream(int n) {stream.resize(n1);ptr 1;}vectorstring insert(int idKey, string value) {stream[idKey] value;vectorstring result;// 如果当前指针指向的 id 已经存储了值则返回从 ptr 开始的最长连续递增序列while (ptr stream.size() !stream[ptr].empty()) {result.push_back(stream[ptr]);ptr;}return result;}
};/*** Your OrderedStream object will be instantiated and called as such:* OrderedStream* obj new OrderedStream(n);* vectorstring param_1 obj-insert(idKey,value);*/
复杂度分析 时间复杂度 每次调用 insert 方法时最坏情况下需要遍历从 ptr 开始的所有连续 id时间复杂度为 O(k)其中 k 是连续 id 的数量。 总体时间复杂度为 O(n)因为每个 id 最多被遍历一次。 空间复杂度 使用了一个大小为 n 1 的数组来存储 (id, value) 对空间复杂度为 O(n)。
示例运行
以下是对示例的运行过程分析 初始化 OrderedStream(5)stream 数组大小为 6ptr 1。 调用 insert(3, cc) 存储 stream[3] cc。 ptr 1stream[1] 为空返回 []。 调用 insert(1, aa) 存储 stream[1] aa。 ptr 1stream[1] 不为空返回 [aa]ptr 更新为 2。 调用 insert(2, bb) 存储 stream[2] bb。 ptr 2stream[2] 不为空返回 [bb]ptr 更新为 3。 调用 insert(5, ee) 存储 stream[5] ee。 ptr 3stream[3] 不为空返回 [cc]ptr 更新为 4。 调用 insert(4, dd) 存储 stream[4] dd。 ptr 4stream[4] 不为空返回 [dd, ee]ptr 更新为 6。 总结
通过使用数组和指针我们可以高效地实现按 id 递增顺序返回值的功能。该方法的时间复杂度和空间复杂度均为 O(n)能够很好地处理流式数据。
