每日一题-设计内存分配器；详细分析思路以及多解法
#我回归了家人们，我将持续更新，并保证高质量内容#
题目取自LeetCode每日一题2502，大家可自行练习或者验证自己思路
题目
给你一个整数
n，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。请你设计一个具备以下功能的内存分配器：
- 分配 一块大小为
size的连续空闲内存单元并赋 idmID。- 释放 给定 id
mID对应的所有内存单元。注意：
- 多个块可以被分配到同一个
mID。- 你必须释放
mID对应的所有内存单元，即便这些内存单元被分配在不同的块中。实现
Allocator类：
Allocator(int n)使用一个大小为n的内存数组初始化Allocator对象。int allocate(int size, int mID)找出大小为size个连续空闲内存单元且位于 最左侧 的块，分配并赋 idmID。返回块的第一个下标。如果不存在这样的块，返回-1。int freeMemory(int mID)释放 idmID对应的所有内存单元。返回释放的内存单元数目。示例：
输入 ["Allocator", "allocate", "allocate", "allocate", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"] [[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]
代码基础框架
class Allocator {
public:
Allocator(int n) {
}
int allocate(int size, int mID) {
}
int freeMemory(int mID) {
}
};
/**
* 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->freeMemory(mID);
*/
题目分析
目标：设计一个内存分配器，支持分配和释放操作。分配时需要找到最左侧的连续空闲块，释放时需清除所有指定ID的内存单元。
关键要求：
我们需要设计一个内存分配器，支持以下功能：
-
分配：找到最左侧的连续
size个空闲内存单元，分配给mID，并返回起始下标。 -
释放：释放所有
mID对应的内存单元，返回释放的数量。
解题思路
1. 问题分析
-
内存表示：用一个数组
arr表示内存单元，arr[i]的值表示第i个内存单元的状态。-
arr[i] == 0：空闲。 -
arr[i] > 0：已分配给某个mID。
-
-
分配逻辑：
-
需要找到最左侧的连续
size个空闲单元。 -
如果找到，将其分配给
mID，并返回起始下标；否则返回-1。
-
-
释放逻辑：
-
遍历数组，将所有
mID对应的单元置为0，并统计释放的数量。
-
2. 破题关键
-
如何找到最左侧的连续空闲块：
-
遍历数组，统计连续空闲单元的数量。
-
当连续空闲单元数量达到
size时，记录起始位置并分配。
-
-
如何高效释放内存：
-
遍历数组，将所有
mID对应的单元置为0，并统计数量。
-
代码逐行解析
1. 初始化
class Allocator {
int[] arr;
public Allocator(int n) {
arr = new int[n]; // 初始化大小为 n 的内存数组，所有单元初始为 0（空闲）
}
}
-
作用：初始化一个大小为
n的内存数组，所有单元初始为0，表示空闲。
2. 分配方法 allocate
public int allocate(int size, int mID) {
int cnt = 0; // 计数器，记录当前连续空闲单元的数量
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) { // 当前单元已被分配
cnt = 0; // 重置计数器
continue;
}
cnt++; // 当前单元空闲，增加计数器
if (cnt == size) { // 找到足够的连续空闲单元
Arrays.fill(arr, i - size + 1, i + 1, mID); // 分配内存
return i - size + 1; // 返回起始下标
}
}
return -1; // 没有找到足够的连续空闲单元
}
-
逻辑：
-
初始化计数器
cnt，用于记录当前连续空闲单元的数量。 -
遍历数组
arr：-
如果当前单元已被分配（
arr[i] > 0），重置计数器cnt = 0。 -
如果当前单元空闲（
arr[i] == 0），增加计数器cnt++。 -
当
cnt == size时，表示找到足够的连续空闲单元：-
使用
Arrays.fill将这段内存单元赋值为mID。 -
返回这段内存块的起始下标
i - size + 1。
-
-
-
如果遍历完数组仍未找到足够的连续空闲单元，返回
-1。
-
-
示例：
-
假设
arr = [0, 0, 0, 0, 0]，调用allocate(2, 1)：-
找到最左侧的连续 2 个空闲单元，分配为
[1, 1, 0, 0, 0]，返回0。
-
-
3. 释放方法 freeMemory
public int freeMemory(int mID) {
int size = 0; // 计数器，记录释放的内存单元数量
for (int i = 0; i < arr.length; i++) {
if (arr[i] == mID) { // 当前单元属于 mID
arr[i] = 0; // 释放内存单元
size++; // 增加计数器
}
}
return size; // 返回释放的内存单元数量
}
-
逻辑：
-
初始化计数器
size，用于记录释放的内存单元数量。 -
遍历数组
arr：-
如果当前单元属于
mID（arr[i] == mID），将其释放（设为0），并增加计数器size++。
-
-
返回
size，表示释放的内存单元数量。
-
-
示例：
-
假设
arr = [1, 1, 0, 2, 2]，调用freeMemory(1)：-
释放所有
mID = 1的单元，变为[0, 0, 0, 2, 2]，返回2。
-
-
复杂度分析
-
分配方法
allocate：-
时间复杂度：
O(n)，最坏情况下需要遍历整个数组。 -
空间复杂度：
O(1)，只使用了常数空间。
-
-
释放方法
freeMemory：-
时间复杂度：
O(n)，需要遍历整个数组。 -
空间复杂度：
O(1)，只使用了常数空间。
-
-
核心思想：通过数组模拟内存单元，遍历处理分配和释放。
-
优点：实现简单，逻辑清晰。
-
缺点：在大规模数据下，时间复杂度较高。
-
优化方向：可以使用更高效的数据结构（如链表或线段树）来管理空闲块，减少时间复杂度。
代码
class Allocator {
int[] arr;
public Allocator(int n) {
arr = new int[n];
}
public int allocate(int size, int mID) {
int cnt = 0;
for(int i = 0; i < arr.length; i++){
if(arr[i] > 0){
cnt = 0;
continue;
}
cnt++;
if(cnt == size){
Arrays.fill(arr, i - size + 1, i + 1, mID);
return i - size + 1;
}
}
return -1;
}
public int freeMemory(int mID) {
int size = 0;
for(int i = 0; i < arr.length; i++){
if(arr[i] == mID){
arr[i] = 0;
size++;
}
}
return size;
}
}
/**
* 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.freeMemory(mID);
*/其余思路代码分享
一、Runtime：28ms
class Allocator {
private int n;
private int[] memory;
public Allocator(int n) {
this.n = n;
this.memory = new int[n];
}
public int allocate(int size, int mID) {
int count = 0;
for (int i = 0; i < n; ++i) {
if (memory[i] != 0) {
count = 0;
} else {
++count;
if (count == size) {
for (int j = i - count + 1; j <= i; ++j) {
memory[j] = mID;
}
return i - count + 1;
}
}
}
return -1;
}
public int freeMemory(int mID) {
int count = 0;
for (int i = 0; i < n; ++i) {
if (memory[i] == mID) {
++count;
memory[i] = 0;
}
}
return count;
}
}二、Runtime：8ms
class Allocator {
int[] arr; // 存放数据, arr[i]到arr[i + len[i] - 1]范围内都是arr[i]数据
int[] len; // 存放数据长度, len[i]不等于0才有效, 表示arr[i]数据的长度
public Allocator(int n) {
this.arr = new int[n]; // 初始化默认都是0
this.len = new int[n];
this.len[0] = n; // 初始mem[0]数据的长度就是n
}
public int allocate(int size, int mID) {
for (int i = 0; i < arr.length; i += len[i]) {
if (arr[i] == 0 && len[i] >= size) {
// 如果当前数据是0且范围足够
if (i + size < arr.length && arr[i + size] == 0) {
// 超过size范围之后还是0，说明当前范围超过size，
// 也可以直接用len[i] > size判断，更新0的长度
len[i + size] = len[i] - size;
}
arr[i] = mID;
len[i] = size;
return i;
}
}
return -1;
}
public int freeMemory(int mID) {
int res = 0;
// 先删掉数据
for (int i = 0; i < arr.length; i += len[i]) {
if (arr[i] == mID) {
res += len[i];
arr[i] = 0;
}
}
// 删掉后为0的范围和其相邻的本来就是0的范围合并
for (int i = 0; i < arr.length; i += len[i]) {
if (arr[i] == 0) {
int j = i + len[i];
while (j < arr.length && arr[j] == 0) {
j += len[j];
}
len[i] = j - i;
}
}
return res;
}
}
/**
* 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.freeMemory(mID);
*/制作不易，感谢你的查阅、关注、评论和点赞
