【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【哈希表】2023C-内存冷热标记【欧弟算法】全网注释最详细分类最全的华为OD真题题解
有LeetCode算法/华为OD考试扣扣交流群可加 948025485
可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1336了解算法冲刺训练
文章目录
- 题目描述与示例
- 题目描述
- 输入描述
- 输出描述
- 示例
- 输入
- 输出
- 说明
- 解题思路
- 代码
- Python
- Java
- C++
- 时空复杂度
- 华为OD算法/大厂面试高频题算法练习冲刺训练
题目描述与示例
题目描述
现代计算机系统中通常存在多级的存储设备,针对海量workload的优化的一种思路是将热点内存页优先放到快速存储层级,这就需要对内存页进行冷热标记。
一种典型的方案是基于内存页的访问频次进行标记,如果统计窗口内访问次数大于等于设定阈值,则认为是热内存页,否则是冷内存页。
对于统计窗口内跟踪到的访存序列和阈值,现在需要实现基于频次的冷热标记。内存页使用页框号作为标识。
输入描述
第一行为输入为N,表示访存序列的记录条数,0
(图片来源网络,侵删)第二行为访存序列,空格间隔的N个内存页框号,页框号范围0-65535,同一页框号可能重复出现,出现的次数即为对应页框号的频次。
第三行为热内存页的频次阈值T,正整数,范围1
输出描述
第一行输出标记为热内存的内存页个数,如果没有被标记为热内存的,则输出0。
如果第一行>0,则接下来按照访问频次降序输出内存页框号,一行一个,频次一样的页框号,页框号小的排前面。
示例
输入
10 1 2 1 2 1 2 1 2 1 2 5
输出
2 1 2
说明
内存页1和内存页2均被访问了5次,达到了阈值5,因此热内存页有2个。内存页1和内存页2的访问频次相等,页框号小的排前面。
解题思路
需要记录每一个编号出现的频次,显然应该使用哈希表计数器来进行统计,得到cnt。
(图片来源网络,侵删)统计完之后,还需需根据每一个页面的出现频次和阈值筛去所有的冷内存页,得到新的哈希表cnt_filter。即
cnt = Counter(nums) cnt_filter = {k: v for k, v in cnt.items() if v >= t}
获得cnt_filter中的所有key储存在变量ans中,即为所有的热内存页。
然后对ans进行排序,先按照出现频次逆序排序,再按照编号大小升序排序。即
ans = list(k for k in cnt_filter.keys()) ans.sort(key = lambda k: (-cnt_filter[k], k))
代码
Python
# 题目:【哈希表】2023C-内存冷热标记 # 分值:100 # 作者:许老师-闭着眼睛学数理化 # 算法:哈希表/排序 # 代码看不懂的地方,请直接在群上提问 from collections import Counter # 输入数组长度 n = int(input()) # 输入内存页框号数组 nums = list(map(int, input().split())) # 输入阈值t t = int(input()) # 计算nums中每一个编号的出现次数 cnt = Counter(nums) # 将cnt中所有v小于t的k过滤掉,cnt_filter中均为出现次数大于等于阈值t的k cnt_filter = {k: v for k, v in cnt.items() if v >= t} # cnt_filter的长度即为热内存页的个数 print(len(cnt_filter)) # 获得cnt_filter中的所有编号,构成一个数组 ans = list(k for k in cnt_filter.keys()) # 对ans进行排序,先按照出现频次逆序排序,再按照编号大小升序排序 ans.sort(key = lambda k: (-cnt_filter[k], k)) # 对ans排序完毕后,逐行输出num for num in ans: print(num)
Java
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] nums = new int[n]; for (int i = 0; i = t) { cntFilter.put(entry.getKey(), entry.getValue()); } } System.out.println(cntFilter.size()); List ans = new ArrayList(cntFilter.keySet()); ans.sort((a, b) -> { int freqCompare = cntFilter.get(b).compareTo(cntFilter.get(a)); if (freqCompare == 0) { return a.compareTo(b); } return freqCompare; }); for (int num : ans) { System.out.println(num); } } }
C++
#include #include #include #include using namespace std; int main() { int n; cin >> n; vector nums(n); for (int i = 0; i > nums[i]; } int t; cin >> t; unordered_map cnt; for (int num : nums) { cnt[num]++; } unordered_map cntFilter; for (auto& kv : cnt) { if (kv.second >= t) { cntFilter[kv.first] = kv.second; } } cout ans.push_back(kv.first); } sort(ans.begin(), ans.end(), [&](int a, int b) { if (cntFilter[a] == cntFilter[b]) { return a
还没有评论,来说两句吧...