解題說明
Design Memory Allocator
題目描述：
設計一個記憶體分配器，管理一塊由 n 個連續記憶體單元組成的記憶體。支援兩個操作：allocate(size, mID) 找到最左邊的 size 個連續空閒單元，將它們分配給 mID 並返回第一個單元的索引（找不到返回 -1）；freeMemory(mID) 釋放所有分配給 mID 的單元，返回釋放的單元數量。
解題思路： 由於 n 最大只有 1000，可以直接模擬。使用一個陣列記錄每個單元的分配 ID（0 表示空閒）。
allocate：掃描陣列找最左邊的連續 size 個空閒單元。 freeMemory：遍歷陣列，將所有等於 mID 的單元設為 0。
C++ 解法
複雜度分析
時間複雜度：allocate O(n)；freeMemory O(n) — 其中 n 為記憶體大小
空間複雜度：O(n) — 儲存記憶體狀態的陣列
虛擬碼
1. Initialize array mem[0..n-1] = 0 (all free) 2. allocate(size, mID): a. Scan left to right, count consecutive free cells b. When count reaches size, mark those cells with mID c. Return starting index, or -1 if not found 3. freeMemory(mID): a. Scan array, set all cells with mID to 0 b. Return count of freed cells
其他解法
-
區間集合法（Interval Set）：用
set<pair<int,int>>維護空閒區間，用map<int, vector<pair<int,int>>>記錄每個 mID 的分配區間。allocate 在空閒區間中找第一個夠大的（First Fit）。freeMemory 將 mID 的區間歸還並合併相鄰空閒區間。allocate O(log n)，freeMemory O(k log n)（k 為該 mID 的區間數）。 -
鏈結串列法：用鏈結串列維護空閒和已分配的區間，適合大規模記憶體管理但本題 n <= 1000 不需要。
延伸思考
- 如果 n 可以到 10^6 且操作次數到 10^5，暴力模擬會超時，如何用區間集合法優化？
- 如果要支援「合併碎片」操作（將所有已分配的記憶體移到前面），如何設計？
- 真實的記憶體分配器如何處理碎片化問題（Best Fit vs First Fit vs Buddy System）？