[LeetCode] 每日一题 2502. 设计内存分配器

题目链接

https://leetcode.cn/problems/design-memory-allocator

题目描述

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

1. 分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。

2. 释放 给定 id mID 对应的所有内存单元。

注意：

• 多个块可以被分配到同一个 mID 。

• 你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

• Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。

• int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于  最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。

• int freeMemory(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

示例输入

示例

输入
["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]

解释
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.freeMemory(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.freeMemory(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.freeMemory(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。

提示

• 1 <= n, size, mID <= 1000

• 最多调用 allocate 和 free 方法 1000 次

解题思路

本题要求我们实现一个内存分配器，提供两个操作：分配一块连续的内存区域和释放指定内存块。对于分配操作，我们需要遍历内存数组，找到连续空闲的区域；对于释放操作，则需要根据给定的 ID 释放所有相关内存单元

我选择使用一个数组 memory 来模拟内存空间，所有初始值为0表示空闲。在 allocate 方法中，我从头遍历数组，寻找足够大小的连续空闲内存并分配给指定的 ID。如果找到合适的区域，就用给定的 mID 填充内存。对于 freeMemory 方法，我们遍历整个内存数组，释放所有与 mID 对应的内存单元

代码实现

class Allocator {
    private final int[] memory;

    public Allocator(int n) {
        memory = new int[n];
    }

    public int allocate(int size, int mID) {
        int count = 0;
        int start = -1;
        for (int i = 0; i < memory.length; i++) {
            if (memory[i] != 0) {
                count = 0;
                continue;
            }
            count++;
            if (count == size) {
                Arrays.fill(memory, i - size + 1, i + 1, mID);
                return i - size + 1;
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        int count = 0;
        for (int i = 0; i < memory.length; i++) {
            if (memory[i] == mID) {
                count++;
                memory[i] = 0;
            }
        }
        return count;
    }
}

复杂度分析

• 时间复杂度：

  • allocate 方法的时间复杂度是 O(n)，因为我们需要遍历内存数组，找到连续空闲的内存块

  • freeMemory 方法的时间复杂度也是 O(n)，因为我们需要遍历整个内存数组，释放指定 ID 对应的所有内存单元

• 空间复杂度：O(n)，因为我们使用一个大小为 n 的数组来存储所有元素

总结

本题通过设计一个简单的内存分配器，模拟了内存分配和释放的基本操作。代码实现通过遍历内存数组找到合适的内存块进行分配，释放时同样遍历整个数组，清除指定 ID 对应的内存单元。该方法简单直观，但在性能上有一定限制，适用于内存块较小的场景

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。