Leetcode.2502 设计内存分配器
题目链接
Leetcode.2502 设计内存分配器 Rating : 1746
题目描述
给你一个整数 n ,表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。
请你设计一个具备以下功能的内存分配器:
- 分配 一块大小为
size
的连续空闲内存单元并赋 idmID
。 - 释放 给定 id
mID
对应的所有内存单元。
注意:
- 多个块可以被分配到同一个
mID
。 - 你必须释放
mID
对应的所有内存单元,即便这些内存单元被分配在不同的块中。
实现 Allocator
类:
Allocator(int n)
使用一个大小为n
的内存数组初始化Allocator
对象。int allocate(int size, int mID)
找出大小为size
个连续空闲内存单元且位于 最左侧 的块,分配并赋 idmID
。返回块的第一个下标。如果不存在这样的块,返回 -1 。int free(int mID)
释放 idmID
对应的所有内存单元。返回释放的内存单元数目。
示例:
输入
[“Allocator”, “allocate”, “allocate”, “allocate”, “free”, “allocate”, “allocate”, “allocate”, “free”, “allocate”, “free”]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
输出
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]
解释
Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组,所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
loc.free(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ,因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
loc.free(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ,因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块,所有返回 -1 。
loc.free(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状,因为不存在 mID 为 7 的内存单元。返回 0 。
提示:
- 1 < = n , s i z e , m I D < = 1000 1 <= n, size, mID <= 1000 1<=n,size,mID<=1000
- 最多调用
allocate
和free
方法 1000 次
解法:哈希表模拟
用一个布尔数组 st
,st[i] == true
说明 i
这个位置已经被分配了;否则没有被分配。
用一个哈希表 m
,m
的 key
存储 mID
,m
的value
就存储被分配 mID
的若干个二元组(因为同一个 mID
可能被分配多块不连续的区间),二元组就记录区间的 [l , r]
。
时间复杂度: O ( n ) O(n) O(n)
C++代码:
using PII = pair<int,int>;
class Allocator {
public:
unordered_map<int,vector<PII>> m;
vector<bool> st;
int n;
Allocator(int n) {
//初始 st 和 n
st.resize(n);
this->n = n;
}
int allocate(int size, int mID) {
int idx = -1;
for(int i = 0;i < n;i++){
//寻找还没有被分配的 且连续空间 >= size 的区间
if(!st[i]){
int j = i + 1;
while(j < n && !st[j]) j++;
if(j - i >= size){
idx = i;
break;
}
i = j - 1;
}
}
//若 idx == -1 说明不存在这样的连续空间 直接返回-1即可
if(idx == -1) return -1;
//分配空间
for(int i = idx;i < idx + size;i++) st[i] = true;
//记录 mID 对应的区间 [idx , idx + size - 1]
m[mID].push_back({idx,idx + size - 1});
return idx;
}
int free(int mID) {
int ans = 0;
//释放空间 记录答案
for(auto p:m[mID]){
int l = p.first , r = p.second;
for(int i = l;i <= r;i++) st[i] = false;
ans += r - l + 1;
}
//哈希表中的记录也要移除
m.erase(mID);
return ans;
}
};
/**
* Your Allocator object will be instantiated and called as such:
* Allocator* obj = new Allocator(n);
* int param_1 = obj->allocate(size,mID);
* int param_2 = obj->free(mID);
*/