获取网络忙时数据（100分） - 华为机试真题题解

考试平台： 时习知

分值： 100分

考试时间： 两小时（共3题）

题目描述

工程师小王想要从海量的网络数据中，筛选出忙时数据。

由于是海量数据，小王没办法对海量数据进行排序，再取topN的忙时数据(将数据从大到小排序，取前N个)。

聪明的小王想到了使用固定大小的优先级队列来进行数据筛选。为了场景简化，我们用正整数集来表示海量的网络数据，同时只取N个忙时数据，也即只取N个最大的正整数。

针对每一批数据输入，单独输出一行结果，直接将N个正整数拼接完完整的一行字符串输出即可。

输入

第一行是正整数N和M，N为忙时个数，取值范围[1,24]，M为输入的数据行数，范围[1,1000];

接下来M行，每行两个正整数A,B，以空格分隔，表示有A个重复的正整数B，A、B的取值范围[1,2147483647]，如:

3 5
1 5
6 3
2 2
5 4
1 6

输出

输出每增加一批数据对应的队列结果，直接将队列里的所有数据集从大到小拼接成字符串输出。

如上例输入的输出为:

第一次输入1个5，则队列输出为5

第二次输入6个3，则队列输出为533

第三次输入2个2，则队列输出为533

第四次输入5个4，则队列输出为544

第五次输入1个6，则队列输出为654

所以最终的输出结果为:

5
533
533
544
654

示例1

输入：
1 3
2 3
1 6
7 4

输出：
3 
6 
6

解释： 
只保留一个忙时数据。
第一次输入2个3，则队列输出为3
第二次输入1个6，则队列输出为6
第三次输入7个4，则队列输出为6

示例2

输入：
24 3
10 5
5 1
20 8

输出：
5555555555
555555555511111
888888888888888888885555

解释： 
保留24个忙时数据。
第一次输入10个5，则队列输出为5555555555
第二次输入5个1，则队列输出为555555555511111
第三次输入20个8，则队列输出为888888888888888888885555

C++ 题解

#include <bits/stdc++.h>
using namespace std;

//  n 为忙时个数, m 为输入的数据行数
int n, m;

// 初始化一个小顶堆
priority_queue<int, vector<int>, greater<int>> min_heap;

// 记录堆栈中每个元素的值
map<int, int> freq_map;

// 打印结果
void print_result()
{
    for (auto it = freq_map.rbegin(); it != freq_map.rend(); it++) {
        for (int i = 0; i < it->second; i++) {
            cout << it->first;
        }
    }
    cout << endl;
}


int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        // 将a个b加入小顶堆
        for (int j = 0; j < a; j++) {
            if (min_heap.size() < n) {
                min_heap.push(b);
                freq_map[b]++;
            } else {
                // 如果堆已满且当前元素大于堆顶元素，替换堆顶元素
                int top = min_heap.top();
                if (top < b) {
                    min_heap.pop();
                    min_heap.push(b);
                    freq_map[top]--;
                    freq_map[b]++;
                }
            }
        }

        print_result();
    }

    return 0;
}

代码解释

1. 小顶堆的作用：小顶堆用于维护当前的前N个最大值。当一个新元素进来时，如果堆没有满，则直接加入；如果堆已满且新元素比堆顶元素大，则用新元素替换堆顶元素。这保证了堆中的元素总是当前前N大的。
2. freq_map 的作用：freq_map用于记录每个元素在堆中的频率。因为堆中可能有重复元素，这个map能让我们准确地知道当前堆中有哪些元素及其出现的次数，从而能够正确地生成输出。
3. 输出结果：输出结果要求从大到小输出当前堆中的元素，且每个元素输出的次数要与其在堆中的出现次数一致。通过freq_map和反向遍历map，实现了这个需求。

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏