【华为OD题库-012】模拟消息队列-Java

题目

让我们来模拟一个消息队列的运作，有一个发布者和若干消费者，发布者会在给定的时刻向消息队列发送消息。>若此时消息队列有消费者订阅，这个消息会被发送到订阅的消费者中优先级最高(输入中消费者按优先级升序排列)的一个。>若此时没有订阅的消费者，该消息被消息队列丢弃。消费者则会在给定的时刻订阅消息队列或取消订阅。当消息发送和订阅发生在同一时刻时，先处理订阅操作，即同一时刻订阅的消费者成为消息发送的候选。当消息发送和取消订阅发生在同一时刻时，先处理取消订阅操作，即消息不会被发送到同一时刻取消订阅的消费者。
输入描述
输入为两行
第一行为2N个正整数，代表发布者发送的N个消息的时刻和内容。为方便解折，消息内容也用正整数表示)。第一个数字是第一个消息的发送时刻，第二个数字是第一个消息的内容，以此类推。用例保证发送时刻不会重复，但注意消息并没有按照发送时刻排列。
第二行为2M个正整数，代表M个消费者订阅和取消订阅的时刻。第一个数字是第一个消费者订阅的时刻，第二个数字是第一个消费者取消订阅的时刻，以此类推。用例保证每个消费者的取消订阅时刻大于订阅时刻，消费者按优先级升序排列
两行的数字都由空格分隔。N不超过100，M不超过10，每行的长度不超过1000字符.
输出描述
输出为M行，依次为M个消费者收到的消息内容，消息内容按收到的顺序排列，且由空格分隔:若某个消费者没有收到任何消息，则对应的行输出-1.
示例1:
输入
2 22 1 11 4 44 5 55 3 33
1 7 2 3
输出
11 33 44 55
22
说明
消息11在1时刻到达，此时只有第一个消费者订阅，消息发送给它；
消息22在2时刻到达，此时两人消费者都订阅了，消息发送给优先级最高的第2二个消费者；
消息33在时刻3到达，此时只有第一个消费者订阅，消息发送给它；
余下的消息按规则也是发送给第一个消费者
示例2:
输入
5 64 11 64 9 97
9 11 4 9
输出
97
64
消息64在5时刻到达，此时只有第二个消费者订阅，消息发送给它
消息97在9时刻到达，此时只有第一消费者订阅(因为第二个消费者刚好在9时刻取消订阅)，消息发送给它。
11时刻也到达了一个内容为64的消息，不过因为没有消费者订阅，消息被丢弃

思路

题目要求消息内容按收到的顺序排列，所以首先需要将消息按照发送时间排序，比如示例1的消息2 22 1 11 4 44 5 55 3 33排序后的结果应该是：1 11 2 22 3 33 4 44 5 55.
对排序后的消息队列，遍历所有时刻，（i=0;i<len;i+=2）,如果这个时刻在[订阅,取消订阅区间内），注意根据题目要求是左闭右开的区间，那么消息有可能发送给这个订阅者。
当存在多个区间满足上述条件时，需要选择高优先级的订阅者，即靠右边的订阅者。也就是说，可以从右边订阅者开始找，找到第一个满足条件的区间，那么消息将发送给该区间对应的订阅者。
最后的结果是要返回每个订阅者接收到的消息，消息有可能是多个，所以可以用一个二维数组来存储结果：String[][] res。
定义：第一行输入代表消息队列，存入的String[] messages；第二行输入代表订阅者，存入String [] subscriber

先将messages按照发送时间排序
外层遍历messages，（i=0;i<messages.length-1;i+=2）,messages[i]代表发送时刻，messages[i+1]代表该时刻发送的消息。
内存遍历subscriber；从右向左遍历（j=subscriber.length - 2;j>=0;j -=2）,subscriber[j]代表第j/2个订阅者订阅的时刻，subscriber[j+1]代表第j/2个订阅者取消订阅的时刻。
找到第一个满足条件的订阅区间，也就是如果不满足条件，j继续向左移动。不满足条件的区间表达式为：messages[i] < subscriber[j] || messages[i] >= subscriber[j + 1]，即消息发送时间不在订阅区间内（左闭右开）
找到满足条件的区间后，需要将消息messages[i+1]存在第j/2个订阅者中。res[j/2]也是一个数组，代表第j/2个订阅者收到的消息列表，现在需要考虑当前得到的消息应该存在res[j/2]中的哪个索引位置。很明显，如果是第一个消息，那么我们就存放在第一个位置，第二个消息，就存放第二个位置，以此类推。所以需要一个变量来记录当前消费者收到了多少个消息。我们可以用res[j/2][0]来存储第j/2个消费者收到的消息数量，res[j/2][1-n]来存放第j/2个消费者收到的第1~n个消息。
得到res后，再遍历打印输出即可。注意如果res[i][0]=0，那么代表第i个消费者接收到的消息数量为0，该消费者应该输出-1。

题解

java">package hwod;


import java.util.Arrays;
import java.util.Scanner;

public class SimulationMessageQueue {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line1 = sc.nextLine();
        String line2 = sc.nextLine();
        int[] s1 = Arrays.stream(line1.split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] s2 = Arrays.stream(line2.split(" ")).mapToInt(Integer::parseInt).toArray();
        String[] res = getMessages(s1, s2);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }
    }

    private static String[] getMessages(int[] s1, int[] s2) {
        for (int i = 0; i < s1.length - 3; i += 2) {
            for (int j = i + 2; j < s1.length - 1; j += 2) {
                if (s1[i] > s1[j]) {
                    switchLocation(i, j, s1);
                    switchLocation(i + 1, j + 1, s1);
                }
            }
        }
        int len = s2.length / 2, messageMaxSize = s1.length / 2;
        int[][] res = new int[len][messageMaxSize + 1];
        for (int i = 0; i < s1.length - 1; i += 2) {
            int j = s2.length - 2;
            while (j >= 0 && (s1[i] < s2[j] || s1[i] >= s2[j + 1])) j -= 2;
            if (j >= 0) {
                res[j / 2][1 + res[j / 2][0]++] = s1[i + 1];
            }
        }
        String[] ans = new String[len];
        for (int i = 0; i < len; i++) {
            int curSize = res[i][0];
            if (curSize == 0) {
                ans[i] = "-1";
                continue;
            }
            StringBuilder sb = new StringBuilder();
            for (int j = 1; j <= curSize; j++) {
                if (j != 1) sb.append(" ");
                sb.append(res[i][j]);
            }
            ans[i] = sb.toString();
        }
        return ans;


    }

    private static void switchLocation(int i, int j, int[] s1) {
        int temp = s1[i];
        s1[i] = s1[j];
        s1[j] = temp;
    }
}