There are n
(id, value)
pairs, where id
is an integer between 1
and n
and value
is a string. No two pairs have the same id
.
Design a stream that takes the n
pairs in an arbitrary order, and returns the values over several calls in increasing order of their ids.
Implement the OrderedStream
class:
OrderedStream(int n)
Constructs the stream to taken
values and sets a currentptr
to1
.String[] insert(int id, String value)
Stores the new(id, value)
pair in the stream. After storing the pair:- If the stream has stored a pair with
id = ptr
, then find the longest contiguous incrementing sequence of ids starting withid = ptr
and return a list of the values associated with those ids in order. Then, updateptr
to the lastid + 1
. - Otherwise, return an empty list.
- If the stream has stored a pair with
Example:
Input ["OrderedStream", "insert", "insert", "insert", "insert", "insert"] [[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]] Output [null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]] Explanation OrderedStream os= new OrderedStream(5); os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns []. os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"]. os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"]. os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns []. os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].
Solution: Straight Forward
Time complexity: O(n) in total
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class OrderedStream { public: OrderedStream(int n): data_(n + 1) {} vector<string> insert(int id, string value) { data_[id] = value; vector<string> ans; if (ptr_ == id) while (ptr_ < data_.size() && !data_[ptr_].empty()) ans.push_back(data_[ptr_++]); return ans; } private: int ptr_ = 1; vector<string> data_; }; |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 |
# Author: Huahua class OrderedStream: def __init__(self, n: int): self.data = [None] * (n + 1) self.ptr = 1 def insert(self, id: int, value: str) -> List[str]: self.data[id] = value if id == self.ptr: while self.ptr < len(self.data) and self.data[self.ptr]: self.ptr += 1 return self.data[id:self.ptr] return [] |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment