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

考试平台： 时习知

分值： 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

Java 题解

import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
/**
 * @author code5bug
 */
public class Main {

    // 打印结果
    static void printResult(TreeMap<Integer, Integer> freqMap) {
        StringBuilder result = new StringBuilder();
        for (Map.Entry<Integer, Integer> entry : freqMap.descendingMap().entrySet()) {
            int value = entry.getKey();
            int count = entry.getValue();
            for (int i = 0; i < count; i++) {
                result.append(value);
            }
        }
        System.out.println(result.toString());
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // n 为忙时个数, m 为输入的数据行数
        int n = scanner.nextInt(), m = scanner.nextInt();

        // 初始化一个小顶堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 记录堆栈中每个元素的值
        TreeMap<Integer, Integer> freqMap = new TreeMap<>();

        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            // 将a个b加入小顶堆
            for (int j = 0; j < a; j++) {
                if (minHeap.size() < n) {