刷题笔记合集🔗

问题描述

现代计算机系统中通常存在多级的存储设备。为了优化性能,需要将热点内存页优先放到快速存储层级,这就需要对内存页进行冷热标记。

一种典型的方案是基于内存页的访问频次进行标记:

• 如果在统计窗口内访问次数≥阈值,则标记为热内存页
• 否则标记为冷内存页

请实现这个内存页冷热标记的功能。

输入格式

第一行输入一个整数N,表示访存序列的记录条数。

第二行输入N个整数,表示访存序列中的页框号。

第三行输入一个整数T,表示热内存的频次阈值。

输出格式

第一行输出热内存页的个数。

如果存在热内存页,则按以下规则输出页框号:

1. 按访问频次降序排序
2. 频次相同时按页框号升序排序
3. 每个页框号占一行

数据范围

• 0 < N ≤ 10000
• 0 ≤ 页框号 ≤ 65535
• 1 ≤ T ≤ 10000

样例1

输入:

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

输出:

2
1
2

说明:

• 页框号1和2都被访问了5次,达到阈值
• 它们的访问频次相同,按页框号升序输出

样例2

输入:

5
1 2 3 4 5
3

输出:

0

说明:

• 所有页框号的访问频次都是1
• 没有达到阈值3的页框号
• 所以输出0

题解

这道题目可以使用哈希表来解决:

1. 统计每个页框号的访问频次
2. 筛选出频次≥阈值的页框号
3. 按要求排序并输出:
   • 优先按频次降序
   • 频次相同时按页框号升序

时间复杂度为 ,其中 是不同页框号的数量。

参考代码

# 读取输入
n = int(input())
pages = list(map(int, input().split()))
threshold = int(input())

# 统计访问频次
count = {}
for page in pages:
    count[page] = count.get(page, 0) + 1

# 筛选热页
hot_pages = [(page, freq) for page, freq in count.items() if freq >= threshold]

# 输出结果
print(len(hot_pages))

# 按要求排序并输出
if hot_pages:
    hot_pages.sort(key=lambda x: (-x[1], x[0]))
    for page, _ in hot_pages:
        print(page)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        
        // 统计访问频次
        Map<Integer, Integer> count = new HashMap<>();
        for(int i = 0; i < n; i++) {