请求内存算法题

题意描述

有两个数组输入：
mem = [32,128,64,192,256]表示有数组长度个设备，每个设备能提供分配的内存大小值(均为4的倍数)，数组最大长度200000 
reques =[64,128,128,128,512]表示请求内存，在mem中找与请求内存大小最相近或相等的内存设备进行分配，分配成功返回分配的mem数组下标，mem对应设备内存减去已分配出去的空间大小(最小值为0，既已全部分配出去），没有找到可分配的空间，返回-1，如何两个设备内存大小相等，优先分配index比较小的内存，reques最大长度200000
如上传入mem和reques后返回为：res = [2,1,3,4,-1] 

Python实现

# 定义内存分配函数，接受可用内存块和请求内存大小的列表，返回分配结果
def allocate_memory(mem, requests):res = []  # 存储分配结果的列表mem_set = set()  # 存储所有可用内存块，使用元组 (mem_value, index)# 初始化 set，存储所有可用内存块for i in range(len(mem)):if mem[i] > 0:mem_set.add((mem[i], i))  # 将大于0的内存块插入set# 处理每个请求for req in requests:# 查找 ≥ req 的最小内存块it = next(filter(lambda x: x[0] >= req, sorted(mem_set)), None)if it is not None:index = it[1]res.append(index)  # 记录分配的下标# 更新 mem 和 setmem_set.remove(it)  # 从set中移除已分配的内存块mem[index] -= req  # 减少分配后剩余的内存if mem[index] > 0:mem_set.add((mem[index], index))  # 如果还有剩余内存，重新插入setelse:res.append(-1)  # 无法分配，记录-1return res  # 返回分配结果if __name__ == "__main__":mem = [32, 128, 64, 96, 256]  # 可用内存块大小requests = [64, 64, 32, 128, 512]  # 请求内存大小result = allocate_memory(mem, requests)  # 调用分配函数print("Allocation results:", end=" ")  # 输出提示信息for r in result:print(r, end=" ")  # 输出每个请求的分配结果print()  # 换行

C++实现

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>using namespace std;// 定义内存分配函数，接受可用内存块和请求内存大小的向量，返回分配结果
vector<int> allocateMemory(vector<int>& mem, vector<int>& requests) {vector<int> res; // 存储分配结果的向量set<pair<int, int>> memSet; // {mem_value, index}，存储所有可用内存块// 初始化 set，存储所有可用内存块for (int i = 0; i < mem.size(); ++i) {if (mem[i] > 0) {memSet.insert({mem[i], i}); // 将大于0的内存块插入set}}// 处理每个请求for (int req : requests) {auto it = memSet.lower_bound({req, -1}); // 查找 ≥ req 的最小内存块if (it != memSet.end()) {int index = it->second;res.push_back(index); // 记录分配的下标// 更新 mem 和 setmemSet.erase(it); // 从set中移除已分配的内存块mem[index] -= req; // 减少分配后剩余的内存if (mem[index] > 0) {memSet.insert({mem[index], index}); // 如果还有剩余内存，重新插入set}} else {res.push_back(-1); // 无法分配，记录-1}}return res; // 返回分配结果
}int main() {vector<int> mem = {32, 128, 64, 96, 256}; // 可用内存块大小vector<int> requests = {64, 64, 32, 128, 512}; // 请求内存大小vector<int> result = allocateMemory(mem, requests); // 调用分配函数cout << "Allocation results: "; // 输出提示信息for (int r : result) {cout << r << " "; // 输出每个请求的分配结果}cout << endl; // 换行return 0; // 主函数返回值
}

Java实现

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;public class MemoryAllocator {// 定义内存分配函数，接受可用内存块和请求内存大小的列表，返回分配结果public static List<Integer> allocateMemory(List<Integer> mem, List<Integer> requests) {List<Integer> res = new ArrayList<>(); // 存储分配结果的列表Set<Pair> memSet = new TreeSet<>(); // {mem_value, index}，存储所有可用内存块// 初始化 set，存储所有可用内存块for (int i = 0; i < mem.size(); ++i) {if (mem.get(i) > 0) {memSet.add(new Pair(mem.get(i), i)); // 将大于0的内存块插入set}}// 处理每个请求for (int req : requests) {Pair searchPair = new Pair(req, -1);Pair it = memSet.ceiling(searchPair); // 查找 ≥ req 的最小内存块if (it != null) {int index = it.index;res.add(index); // 记录分配的下标// 更新 mem 和 setmemSet.remove(it); // 从set中移除已分配的内存块mem.set(index, mem.get(index) - req); // 减少分配后剩余的内存if (mem.get(index) > 0) {memSet.add(new Pair(mem.get(index), index)); // 如果还有剩余内存，重新插入set}} else {res.add(-1); // 无法分配，记录-1}}return res; // 返回分配结果}public static void main(String[] args) {List<Integer> mem = List.of(32, 128, 64, 96, 256); // 可用内存块大小List<Integer> requests = List.of(64, 64, 32, 128, 512); // 请求内存大小List<Integer> result = allocateMemory(new ArrayList<>(mem), new ArrayList<>(requests)); // 调用分配函数System.out.print("Allocation results: "); // 输出提示信息for (int r : result) {System.out.print(r + " "); // 输出每个请求的分配结果}System.out.println(); // 换行}// 自定义 Pair 类用于存储内存值和索引static class Pair implements Comparable<Pair> {int value;int index;Pair(int value, int index) {this.value = value;this.index = index;}@Overridepublic int compareTo(Pair other) {if (this.value != other.value) {return Integer.compare(this.value, other.value);}return Integer.compare(this.index, other.index);}}
}