題目：

有?n?個(gè)?(id, value)?對(duì)，其中?id?是?1?到?n?之間的一個(gè)整數(shù)，value?是一個(gè)字符串。不存在?id?相同的兩個(gè)?(id, value)?對(duì)。

設(shè)計(jì)一個(gè)流，以?任意?順序獲取?n?個(gè)?(id, value)?對(duì)，并在多次調(diào)用時(shí)?按?id?遞增的順序?返回一些值。

實(shí)現(xiàn)?OrderedStream?類：

• OrderedStream(int n)?構(gòu)造一個(gè)能接收?n?個(gè)值的流，并將當(dāng)前指針?ptr?設(shè)為?1?。
• String[] insert(int id, String value)?向流中存儲(chǔ)新的?(id, value)?對(duì)。存儲(chǔ)后：
  • 如果流存儲(chǔ)有?id = ptr?的?(id, value)?對(duì)，則找出從?id = ptr?開始的?最長(zhǎng) id 連續(xù)遞增序列?，并?按順序?返回與這些 id 關(guān)聯(lián)的值的列表。然后，將?ptr?更新為最后那個(gè)??id + 1?。

  • 否則，返回一個(gè)空列表。

示例：

輸入
["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?僅由小寫字母組成
• 每次調(diào)用?insert?都會(huì)使用一個(gè)唯一的?id
• 恰好調(diào)用?n?次?insert

解法：基于數(shù)組和指針的流式處理

解題思路

我們需要設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，能夠按?id?遞增的順序返回?(id, value)?對(duì)的值。由于?id?是唯一的且范圍固定（1?到?n），我們可以使用一個(gè)數(shù)組來存儲(chǔ)這些值，并通過一個(gè)指針?ptr?來跟蹤當(dāng)前可以返回的最小?id。

具體步驟如下：

1. 初始化：

   • 使用一個(gè)大小為?n + 1?的數(shù)組?stream?來存儲(chǔ)?(id, value)?對(duì)。數(shù)組的索引直接對(duì)應(yīng)?id，方便快速訪問。

   • 初始化指針?ptr?為?1，表示下一個(gè)需要返回的?id?是?1。

2. 插入操作：

   • 將?(idKey, value)?對(duì)存儲(chǔ)到數(shù)組?stream?的?idKey?位置。

   • 檢查當(dāng)前指針?ptr?是否指向一個(gè)已經(jīng)存儲(chǔ)了值的?id。如果是，則從?ptr?開始，依次檢查連續(xù)的?id?是否已經(jīng)存儲(chǔ)，并將對(duì)應(yīng)的?value?加入結(jié)果列表。

   • 更新指針?ptr?為最后一個(gè)連續(xù)?id?的下一個(gè)位置。

   • 返回結(jié)果列表。

代碼實(shí)現(xiàn)

class OrderedStream {
private:vector<string> stream;  // 用于存儲(chǔ) (id, value) 對(duì)的數(shù)組int ptr;                // 當(dāng)前指針，指向下一個(gè)應(yīng)該返回的 idpublic:OrderedStream(int n) {stream.resize(n+1);ptr = 1;}vector<string> insert(int idKey, string value) {stream[idKey] = value;vector<string> result;// 如果當(dāng)前指針指向的 id 已經(jīng)存儲(chǔ)了值，則返回從 ptr 開始的最長(zhǎng)連續(xù)遞增序列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);* vector<string> param_1 = obj->insert(idKey,value);*/

復(fù)雜度分析

1. 時(shí)間復(fù)雜度：

   • 每次調(diào)用?insert?方法時(shí)，最壞情況下需要遍歷從?ptr?開始的所有連續(xù)?id，時(shí)間復(fù)雜度為?O(k)，其中?k?是連續(xù)?id?的數(shù)量。

   • 總體時(shí)間復(fù)雜度為?O(n)，因?yàn)槊總€(gè)?id?最多被遍歷一次。

2. 空間復(fù)雜度：

   • 使用了一個(gè)大小為?n + 1?的數(shù)組來存儲(chǔ)?(id, value)?對(duì)，空間復(fù)雜度為?O(n)。

示例運(yùn)行

以下是對(duì)示例的運(yùn)行過程分析：

1. 初始化?OrderedStream(5)，stream?數(shù)組大小為?6，ptr = 1。

2. 調(diào)用?insert(3, "cc")：

   • 存儲(chǔ)?stream[3] = "cc"。

   • ptr = 1，stream[1]?為空，返回?[]。

3. 調(diào)用?insert(1, "aa")：

   • 存儲(chǔ)?stream[1] = "aa"。

   • ptr = 1，stream[1]?不為空，返回?["aa"]，ptr?更新為?2。

4. 調(diào)用?insert(2, "bb")：

   • 存儲(chǔ)?stream[2] = "bb"。

   • ptr = 2，stream[2]?不為空，返回?["bb"]，ptr?更新為?3。

5. 調(diào)用?insert(5, "ee")：

   • 存儲(chǔ)?stream[5] = "ee"。

   • ptr = 3，stream[3]?不為空，返回?["cc"]，ptr?更新為?4。

6. 調(diào)用?insert(4, "dd")：

   • 存儲(chǔ)?stream[4] = "dd"。

   • ptr = 4，stream[4]?不為空，返回?["dd", "ee"]，ptr?更新為?6。

總結(jié)

通過使用數(shù)組和指針，我們可以高效地實(shí)現(xiàn)按?id?遞增順序返回值的功能。該方法的時(shí)間復(fù)雜度和空間復(fù)雜度均為?O(n)，能夠很好地處理流式數(shù)據(jù)。