力扣每日一题——设计有序流

目录

题目链接：1656. 设计有序流 - 力扣（LeetCode）

题目描述

示例：

提示：

解法一：数组作为数据容器+遍历

核心思路

实现步骤

关键点

示例说明

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

时间复杂度分析

1. 单次 insert 操作的时间复杂度

2. 总体时间复杂度

空间复杂度分析

1. 数组 strs 的空间

2. 返回结果的空间

总结

---

题目链接：1656. 设计有序流 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

有 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 <= 1000
• 1 <= id <= n
• value.length == 5
• value 仅由小写字母组成
• 每次调用 insert 都会使用一个唯一的 id
• 恰好调用 n 次 insert

---

解法一：数组作为数据容器+遍历

核心思路

1. 数据结构：使用数组strs存储元素，指针ptr指示当前应检查的位置。

2. 初始化：数组大小为n+2，确保指针在递增时不会越界。ptr初始化为1，因为元素ID从1开始。

3. 插入操作：

   • 将元素存入数组对应位置。

   • 若当前指针位置元素非空，则连续取出元素直到遇到空值，同时移动指针。

实现步骤

1. 初始化：构造函数创建大小为n+2的数组，ptr初始为1。

2. 插入元素：

   • 将元素放入数组的idKey位置。

   • 检查当前指针位置是否非空。若非空，则从该位置开始连续取出元素，直到遇到空值，同时移动指针。

3. 返回结果：每次插入后，返回从ptr开始的最长连续元素块。

关键点

• 指针管理：ptr始终指向下一个待检查的位置，确保按顺序处理元素。

• 连续块提取：当指针位置有元素时，连续取出后续元素直到中断，保证顺序性。

• 数组大小：设为n+2避免指针越界，适应极端情况（如所有元素插入后指针移动到n+1）。

示例说明

以输入n=5为例：

1. 插入3→检查ptr=1，无元素→返回空。

2. 插入1→ptr=1有元素，取出，ptr移到2→返回["aaaaa"]。

3. 插入2→ptr=2有元素，连续取出2、3→返回["bbbbb","ccccc"]，ptr移到4。

4. 插入5→ptr=4无元素→返回空。

5. 插入4→ptr=4有元素，连续取出4、5→返回["ddddd","eeeee"]。

---

Java写法：

class OrderedStream {int ptr;String[] strs;public OrderedStream(int n) {strs = new String[n + 2];// 0 1 2 3 4 5 6ptr = 1;}public List<String> insert(int idKey, String value) {strs[idKey] = value;if(strs[ptr] == null){// 这里是空的那么就不会找return new ArrayList<>();}// 能走到这里说明这里有值，就要一直到往后找直到没有List<String> strStream = new ArrayList<>();while(strs[ptr] != null){strStream.add(strs[ptr]);ptr++;}return strStream;}
}/*** Your OrderedStream object will be instantiated and called as such:* OrderedStream obj = new OrderedStream(n);* List<String> param_1 = obj.insert(idKey,value);*/

C++写法：

class OrderedStream {
private:int ptr;               // 指针，指向当前需要检查的位置vector<string> strs;   // 存储元素的数组public:OrderedStream(int n) {strs.resize(n + 2); // 初始化数组大小为 n+2ptr = 1;            // 指针初始化为 1}vector<string> insert(int idKey, string value) {strs[idKey] = value; // 将值插入到指定位置vector<string> result;// 如果当前指针位置有值，则连续取出直到遇到空值if (strs[ptr] != "") {while (ptr < strs.size() && strs[ptr] != "") {result.push_back(strs[ptr]); // 将值加入结果ptr++;                       // 移动指针}}return result; // 返回结果}
};/*** Your OrderedStream object will be instantiated and called as such:* OrderedStream* obj = new OrderedStream(n);* vector<string> param_1 = obj->insert(idKey,value);*/

运行时间

时间复杂度和空间复杂度

时间复杂度分析

1. 单次 insert 操作的时间复杂度

• 插入操作：将 value 存入 strs[idKey] 的时间复杂度是 O(1)，因为数组的随机访问是常数时间。

• 连续块提取：从 ptr 开始，连续检查并取出元素，直到遇到空值或超出数组范围。假设连续块的长度为 k，则这部分的时间复杂度是 O(k)。

因此，单次 insert 操作的时间复杂度为 O(k)，其中 k 是连续块的长度。

---

2. 总体时间复杂度

• 假设总共进行了 m 次 insert 操作。

• 每次 insert 操作的时间复杂度为 O(k)，其中 k 是当前连续块的长度。

• 由于每个元素只会被取出一次（即只会被添加到结果中一次），所有 insert 操作中连续块的总长度不会超过 n（数组的总大小）。

因此，m 次 insert 操作的总体时间复杂度为 O(n)。

---

空间复杂度分析

1. 数组 strs 的空间

• 数组 strs 的大小为 n + 2，因此空间复杂度为 O(n)。

2. 返回结果的空间

• 每次 insert 操作返回的结果是一个 vector<string>，其大小取决于连续块的长度 k。

• 由于每个元素只会被返回一次，所有返回结果的总空间复杂度也是 O(n)。

因此，总的空间复杂度为 O(n)。

---

---

总结

嗨嗨嗨