Problem

You are given an integer n representing the size of a 0-indexed memory array. All memory units are initially free.

You have a memory allocator with the following functionalities:

  1. Allocate a block of size consecutive free memory units and assign it the id mID.
  2. Free all memory units with the given id mID.

Note that:

  • Multiple blocks can be allocated to the same mID.
  • You should free all the memory units with mID, even if they were allocated in different blocks.

Implement the Allocator class:

  • Allocator(int n) Initializes an Allocator object with a memory array of size n.
  • int allocate(int size, int mID) Find the leftmost block of size consecutive free memory units and allocate it with the id mID. Return the block’s first index. If such a block does not ext, return -1.
  • int freeMemory(int mID) Free all memory units with the id mID. Return the number of memory units you have freed.

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

Example 1:

Input
["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]]
Output
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]
Explanation

1
2
3
4
5
6
7
8
9
10
11
Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free.
loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes [1,_,_,_,_,_,_,_,_,_]. We return 0.
loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes [1,2,_,_,_,_,_,_,_,_]. We return 1.
loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes [1,2,3,_,_,_,_,_,_,_]. We return 2.
loc.freeMemory(2); // Free all memory units with mID 2. The memory array becomes [1,_, 3,_,_,_,_,_,_,_]. We return 1 since there is only 1 unit with mID 2.
loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes [1,_,3,4,4,4,_,_,_,_]. We return 3.
loc.allocate(1, 1); // The leftmost block's first index is 1. The memory array becomes [1,1,3,4,4,4,_,_,_,_]. We return 1.
loc.allocate(1, 1); // The leftmost block's first index is 6. The memory array becomes [1,1,3,4,4,4,1,_,_,_]. We return 6.
loc.freeMemory(1); // Free all memory units with mID 1. The memory array becomes [_,_,3,4,4,4,_,_,_,_]. We return 3 since there are 3 units with mID 1.
loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1.
loc.freeMemory(7); // Free all memory units with mID 7. The memory array remains the same since there is no memory unit with mID 7. We return 0.

Constraints:

  • 1 <= n, size, mID <= 1000
  • At most 1000 calls will be made to allocate and freeMemory.

Test Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Allocator:

    def __init__(self, n: int):


    def allocate(self, size: int, mID: int) -> int:


    def freeMemory(self, mID: int) -> int:



# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.freeMemory(mID)
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import pytest

from solution import Allocator

null = None


@pytest.mark.parametrize('actions, params, expects', [
    (
        ["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","freeMemory","freeMemory","freeMemory","freeMemory","freeMemory","allocate","allocate","allocate","freeMemory","freeMemory","freeMemory","allocate","allocate","freeMemory","freeMemory","freeMemory","allocate","allocate","freeMemory","allocate","allocate","allocate","freeMemory","freeMemory","freeMemory","freeMemory","freeMemory","freeMemory","freeMemory","allocate","freeMemory","allocate","freeMemory","allocate","allocate","freeMemory","allocate","allocate","freeMemory","freeMemory","allocate","freeMemory","freeMemory","allocate","allocate","allocate","freeMemory","allocate","allocate","freeMemory","freeMemory","allocate","allocate","allocate","freeMemory","allocate","allocate","freeMemory","freeMemory","freeMemory","allocate","freeMemory","freeMemory","freeMemory","freeMemory","allocate","allocate","allocate","freeMemory","allocate","freeMemory","freeMemory","allocate","freeMemory","allocate","freeMemory","freeMemory"],
        [[100],[27],[12],[53],[61],[80],[21,78],[81,40],[50,76],[40],[76],[63],[25,100],[96,12],[92],[92],[84],[19,71],[22,90],[60],[42,79],[26,41],[59,33],[79],[58],[97],[92],[97],[92],[40],[52,74],[40],[53,17],[17],[36,32],[51,13],[41],[5,87],[44,66],[71],[53],[74,14],[78],[14],[32,54],[45,28],[84,47],[16],[100,78],[5,99],[33],[100],[62,79],[31,32],[85,81],[78],[34,45],[47,7],[7],[84],[6],[35,55],[94],[87],[20],[87],[96,60],[40,66],[28,96],[28],[25,2],[100],[96],[19,35],[16],[92,42],[80],[79]],
        [null,0,0,0,0,0,0,-1,21,0,50,0,21,-1,0,0,0,46,65,0,-1,-1,-1,0,0,0,0,0,0,0,-1,0,-1,0,-1,-1,0,87,-1,19,0,-1,21,0,-1,-1,-1,0,-1,0,0,25,-1,5,-1,0,-1,-1,0,0,0,-1,0,5,0,0,-1,-1,36,0,-1,0,28,36,0,-1,0,0],
    ),
])
@pytest.mark.parametrize('clazz', [Allocator])
def test_solution(clazz, actions, params, expects):
    sol = None
    for action, args, expected in zip(actions, params, expects):
        if action == 'Allocator':
            sol = clazz(*args)
        else:
            assert getattr(sol, action)(*args) == expected

Thoughts

已分配的内存可以用字典记录，key 为 mID。因为允许为同一个 mID 多次分配内存，那么 value 就要用一个数组，数组的一个元素为某一次分配的内存空间区间 [start, end)。

再用一个有序数组记录空闲的内存空间，数组的一个元素为一段连续空闲空间的起止位置 [start, end)。

分配内存的时候，从左到右依次扫描每一段连续空闲空间，找到第一段足够大的区间。如果该区间大小刚好等于申请的大小，则直接从数组中删掉。否则把 start 修改为 start + size 即可。

释放内存的时候，从字典中取出 mID 已经分配的内存空间数组，对其中的每一段做释放处理。因为空闲空间数组的有序的，可以用二分法找到待释放区间在空闲空间数组中的插入位置。只是需要注意，释放一段区间前，先要检查它是否跟左边和右边的空闲区间相连，如果相连则需要做合并。

构造方法的时间复杂度 O(1)，allocate 和 freeMemory 的时间复杂度最坏都是 O(n)。空间复杂度最坏是 O(n)。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from bisect import bisect_left


Range = tuple[int, int] # (start, end)


class Allocator:

    def __init__(self, n: int):
        self._free = [(0, n)] # [range of a contiguous free block]
        self._allocated: dict[int, list[Range]] = {} # mID -> [range]

    def allocate(self, size: int, mID: int) -> int:
        if (size, mID) == (28, 96):
            print(self._free, self._allocated)
        for i, (start, end) in enumerate(self._free):
            if end - start >= size:
                if mID not in self._allocated:
                    self._allocated[mID] = []
                self._allocated[mID].append((start, start + size))

                if end - start == size:
                    self._free.pop(i)
                else:
                    self._free[i] = (start + size, end)

                return start

        return -1

    def freeMemory(self, mID: int) -> int:
        if mID not in self._allocated:
            return 0

        total = 0
        units = self._allocated.pop(mID)
        for start, end in units:
            total += end - start
            i = bisect_left(self._free, (start, end))
            if i > 0 and self._free[i - 1][1] == start:
                i -= 1
                start = self._free.pop(i)[0]
            if i < len(self._free) and self._free[i][0] == end:
                end = self._free.pop(i)[1]
            self._free.insert(i, (start, end))

        return total


# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.freeMemory(mID)
medium
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~