设计有序流

难度:

标签:

题目描述

有 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

代码结果

运行时间: 89 ms, 内存: 16.8 MB

/*
 * 思路：
 * 1. 创建一个OrderedStream类，初始化一个String数组用于存储值，并设置指针ptr为1。
 * 2. insert方法接收id和value参数，将value存储到数组的相应位置。
 * 3. 使用Java Stream API检查指针位置的值是否已填充，找到连续非空值。
 * 4. 返回从ptr开始的连续非空值的列表，并更新ptr到第一个未填充的位置。
 */
import java.util.*;
import java.util.stream.Collectors;

public class OrderedStream {
    private String[] stream;
    private int ptr;

    public OrderedStream(int n) {
        stream = new String[n + 1]; // 创建一个大小为n+1的数组
        ptr = 1; // 初始化指针ptr为1
    }

    public List<String> insert(int id, String value) {
        stream[id] = value; // 存储值
        List<String> result = Arrays.stream(stream, ptr, stream.length) // 使用Java Stream API
                                     .filter(Objects::nonNull) // 过滤非空值
                                     .takeWhile(val -> stream[ptr] != null) // 找到连续非空值
                                     .collect(Collectors.toList()); // 收集到结果列表
        ptr += result.size(); // 更新指针
        return result; // 返回结果列表
    }
}

解释

方法:

本题解采用字典存储输入的(id, value)对，并使用一个指针ptr来记录当前应该输出的连续id序列的起始点。插入操作首先将(id, value)对存储到字典中。如果当前插入的id等于ptr，则从该id开始，不断检查并输出连续的id值直到找不到为止，随后更新ptr指向下一个未输出的id。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在OrderedStream的设计中选择使用字典来存储id和value的对应关系，而不是使用数组或其他数据结构？

▷

使用字典存储id和value的对应关系可以方便地处理非连续的id输入，并且可以灵活地插入任意id而不需要考虑数组的大小或者初始化开销。在数组中，如果id范围很大但插入的id很少，会造成大量空间浪费。字典提供了更高的空间效率和灵活性，尤其是在id值不连续或者范围未知的情况下。

🦆

插入操作中，当id不等于ptr时直接返回空列表，这种设计有什么具体的优点或缺点？

▷

这种设计的优点是能够保证只有当我们能够输出一个连续的序列时才返回非空列表，从而确保输出的顺序性和完整性。缺点是，如果数据的输入顺序非常随机，可能会导致多次插入操作都不产生输出，直到某一个特定的id被插入后才输出一大批累积的数据，这在某些情况下可能会导致输出的延迟或者批处理输出，影响性能和即时性。

🦆

在while循环中不断检查连续的id，这种方法是否会影响性能，特别是在id非常分散的情况下？

▷

当id分布非常分散时，这种方法确实可能影响性能。因为每次插入操作都可能需要进行多次查找以确认连续的id，如果这些id间隔较大，则每次插入可能只处理少数几个id，甚至一个都处理不了，导致多次无效查找。这会增加算法的时间复杂度，尤其是在极端情况下，如每次插入的id都非常分散。

🦆

当所有的id都被插入且顺序完全颠倒时，OrderedStream类的表现如何？是否还能有效地返回正确的结果列表？

▷

如果所有的id都被插入且顺序完全颠倒，例如先插入最大的id，再插入次大的id，一直到最小的id，OrderedStream类将在每次插入时都只返回空列表，直到最后一个id（即id 1）被插入。在这个时候，将会输出全部存储的值。这种情况下，OrderedStream类能够有效地返回正确的结果列表，但所有输出将会延迟到最后一个（即第一个按顺序）id被插入时。

设计有序流

题目描述

代码结果

解释

代码细节讲解

相关问题