华为OD机试 - 内存冷热标记（Java 2024 C卷 100分）

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

现代计算机系统通常存在多级的存储设备，针对海量的 wordload 的优化的一种思路是将热点内存页优化先放到快速存储层级，这就需要对内存页进行冷热标记。

一种典型的方案是基于内存页的访问频次进行标记，如果统计窗口内访问次数大于等于设定阈值，要实现基于频次的冷热标记。内存页使用页框号作为标识。

二、输入描述

第一行输入为 N, 表示访存序列的记录条数， 0 < N ≤ 10000。

第二行为访问内存序列，空格间隔的 N 个内存页框号，页面号范围 0 ~ 65535，同一个页框号可能重复出现，出现的次数即为对应框号的频次。

第三行为热内存的频次阈值 T ，正整数范围 1 ≤ T ≤ 10000。

三、输出描述

第一行为输出标记为热内存的内存页个数，如果没有被标记为热内存的，则输出 0。

如果第一行大于 0，则接下来按照访问频次降序输出内存页框号，一行一个，频次一样的页框号，页框号小的排前面。

四、解题思路

读取输入数据，包括访存序列的记录条数N、访问内存序列和热内存的频次阈值T。
统计每个内存页框号的访问频次。
找出访问频次大于等于阈值T的内存页框号，并将它们标记为热内存。
按照访问频次降序输出被标记为热内存的内存页框号。

五、Java算法源码

public class Test03 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt(); // 读取访存序列的记录条数int[] memoryPages = new int[N]; // 存储访问内存序列for (int i = 0; i < N; i++) {memoryPages[i] = sc.nextInt(); // 读取访问内存序列}int T = sc.nextInt(); // 读取热内存的频次阈值// 统计每个内存页框号的访问频次Map<Integer, Integer> frequencyMap = new HashMap<>();for (int page : memoryPages) {frequencyMap.put(page, frequencyMap.getOrDefault(page, 0) + 1);}// 找出访问频次大于等于阈值T的内存页框号，并将它们标记为热内存List<Integer> hotMemoryPages = new ArrayList<>();for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {if (entry.getValue() >= T) {hotMemoryPages.add(entry.getKey());}}// 按照访问频次降序输出被标记为热内存的内存页框号Collections.sort(hotMemoryPages, (a, b) -> {int freqA = frequencyMap.get(a);int freqB = frequencyMap.get(b);if (freqA != freqB) {return freqB - freqA;} else {return a - b;}});System.out.println(hotMemoryPages.size()); // 输出标记为热内存的内存页个数for (int page : hotMemoryPages) {System.out.println(page); // 输出被标记为热内存的内存页框号}}
}