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

素颜马尾好姑娘i 2024-04-20 12:28 11阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

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

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

### 一、题目描述 ###

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

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

### 二、输入描述 ###

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

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

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

### 三、输出描述 ###

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

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

### 四、解题思路 ###

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

### 五、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); // 输出被标记为热内存的内存页框号
            }
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

10  
1 2 1 2 1 2 1 2 1 2  
5

#### 2、输出 ####

2  
1  
2

#### 3、说明 ####

内存页 1 和内存页 2 均被访问了5 次，达到了阈值5 ，因此热内存页有2个。内存页1 和内存页 2 的访问频次相等，页框号小的排前面。

![在这里插入图片描述][8265be55db894761b9132e29f93bb379.bmp_pic_center]

🏆下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

🏆本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

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

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4fb463ee4def48bda406a01ecabee5ac.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[8265be55db894761b9132e29f93bb379.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/8265be55db894761b9132e29f93bb379.bmp#pic_center
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/1349a7a8025e4c4a9e72ee88e7632709.gif