有LeetCode算法/华为OD考试扣扣交流群可加 948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336了解算法冲刺训练
文章目录
题目描述与示例题目描述输入描述输出描述示例输入输出说明
解题思路代码PythonJavaC++时空复杂度
华为OD算法/大厂面试高频题算法练习冲刺训练
题目描述与示例
题目描述
现代计算机系统中通常存在多级的存储设备，针对海量workload的优化的一种思路是将热点内存页优先放到快速存储层级，这就需要对内存页进行冷热标记。
一种典型的方案是基于内存页的访问频次进行标记，如果统计窗口内访问次数大于等于设定阈值，则认为是热内存页，否则是冷内存页。
对于统计窗口内跟踪到的访存序列和阈值，现在需要实现基于频次的冷热标记。内存页使用页框号作为标识。
输入描述
第一行为输入为N，表示访存序列的记录条数，0 < N < 10000。
第二行为访存序列，空格间隔的N个内存页框号，页框号范围0-65535，同一页框号可能重复出现，出现的次数即为对应页框号的频次。
第三行为热内存页的频次阈值T，正整数，范围1< T < 10000
输出描述
第一行输出标记为热内存的内存页个数，如果没有被标记为热内存的，则输出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 < n; i++) {
nums[i] = scanner.nextInt();
}
int t = scanner.nextInt();
Map
for (int num : nums) {
cnt.put(num, cnt.getOrDefault(num, 0) + 1);
}
Map
for (Map.Entry
if (entry.getValue() >= t) {
cntFilter.put(entry.getKey(), entry.getValue());
}
}
System.out.println(cntFilter.size());
List
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
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int t;
cin >> t;
unordered_map
for (int num : nums) {
cnt[num]++;
}
unordered_map
for (auto& kv : cnt) {
if (kv.second >= t) {
cntFilter[kv.first] = kv.second;
}
}
cout << cntFilter.size() << endl;
vector
for (auto& kv : cntFilter) {
ans.push_back(kv.first);
}
sort(ans.begin(), ans.end(), [&](int a, int b) {
if (cntFilter[a] == cntFilter[b]) {
return a < b;
}
return cntFilter[a] > cntFilter[b];
});
for (int num : ans) {
cout << num << endl;
}
return 0;
}
时空复杂度
时间复杂度：O(NlogN)。排序所需时间复杂度。
空间复杂度：O(N)。哈希表所占空间
华为OD算法/大厂面试高频题算法练习冲刺训练
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务300+同学成功上岸！ 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！ 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 & OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
精彩文章
发表评论