华为OD机试真题——模拟消息队列（2025A卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

发布于：2025-04-19 ⋅ 阅读:(28) ⋅ 点赞:(0)

在这里插入图片描述

2025 A卷 100分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

2025华为OD真题目录+全流程解析/备考攻略/经验分享

华为OD机试真题《模拟消息队列》：

目录

题目名称：模拟消息队列

属性 内容
知识点 事件排序、优先级处理、逻辑处理
时间限制 1秒
空间限制 256MB
限定语言 不限

题目描述

模拟一个消息队列的运作，包含一个发布者和若干消费者。发布者在特定时刻发送消息，若此时有消费者订阅，消息将发送给优先级最高的消费者（消费者按输入顺序升序排列，升序即优先级递增）。若没有订阅者，消息被丢弃。消费者在特定时刻订阅或取消订阅，同一时刻的事件处理顺序如下：

  • 订阅操作优先于消息发送
  • 取消订阅优先于消息发送

输入描述
输入为两行：

  1. 第一行：2N个正整数，表示N条消息的发送时刻和内容（时刻不重复，但未按时间排序）。例如：2 22 1 11 4 44代表3条消息，时刻分别为2（内容22）、1（内容11）、4（内容44）。
  2. 第二行：2M个正整数，表示M个消费者的订阅和取消订阅时刻。例如：1 7 2 3代表两个消费者，第一个订阅时刻1、取消时刻7；第二个订阅时刻2、取消时刻3。

输出描述
输出M行，每行为对应消费者收到的消息内容（按接收顺序排列），若未收到消息则输出-1。

测试用例

  1. 输入

    2 22 1 11 4 44 5 55 3 33  
1 7 2 3

    输出

    11 33 44 55  
22

    说明：消息在时刻1、2、3、4、5依次处理，优先级高的消费者（后订阅的）优先接收消息。

  2. 输入

    5 64 11 64 9 97  
9 11 4 9

    输出

    97  
64

Java

问题分析

我们需要模拟消息队列的工作流程，其中发布者在特定时刻发送消息，消费者在特定时刻订阅或取消订阅。消息发送时，优先发送给当前活跃且优先级最高的消费者。优先级由消费者的输入顺序决定，后订阅的消费者优先级更高。

解决思路

  1. 事件收集与排序：将所有订阅、取消订阅、消息发送事件按时间排序，同一时刻的事件按订阅 → 取消 → 消息的顺序处理。
  2. 维护活跃消费者：使用 TreeSet 维护当前活跃的消费者，按优先级（输入顺序的逆序）排序。
  3. 消息分发：处理消息事件时，将消息发送给当前优先级最高的消费者。

Java 代码实现

import java.util.*;

public class Main {
    static class Event implements Comparable<Event> {
        int time;       // 事件发生时间
        int type;       // 0:订阅, 1:取消订阅, 2:消息
        int consumerIdx; // 消费者索引（用于订阅/取消）
        int message;     // 消息内容（仅消息事件有效）

        public Event(int time, int type, int consumerIdx, int message) {
            this.time = time;
            this.type = type;
            this.consumerIdx = consumerIdx;
            this.message = message;
        }

        @Override
        public int compareTo(Event other) {
            if (this.time != other.time) {
                return Integer.compare(this.time, other.time);
            } else {
                return Integer.compare(this.type, other.type); // 订阅→取消→消息
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 解析消息输入
        String[] msgInput = scanner.nextLine().split(" ");
        List<Event> events = new ArrayList<>();
        for (int i = 0; i < msgInput.length; i += 2) {
            int time = Integer.parseInt(msgInput[i]);
            int msg = Integer.parseInt(msgInput[i + 1]);
            events.add(new Event(time, 2, -1, msg)); // 类型2是消息事件
        }

        // 解析消费者输入
        String[] consumerInput = scanner.nextLine().split(" ");
        int m = consumerInput.length / 2;
        List<List<Integer>> consumerMsgs = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int subTime = Integer.parseInt(consumerInput[2 * i]);
            int unsubTime = Integer.parseInt(consumerInput[2 * i + 1]);
            events.add(new Event(subTime, 0, i, -1));  // 订阅事件
            events.add(new Event(unsubTime, 1, i, -1)); // 取消事件
            consumerMsgs.add(new ArrayList<>()); // 初始化消费者的消息列表
        }

        // 按时间排序所有事件
        Collections.sort(events);

        // 维护当前活跃的消费者（按优先级降序排列）
        TreeSet<Integer> activeConsumers = new TreeSet<>(Collections.reverseOrder());

        // 处理所有事件
        for (Event event : events) {
            switch (event.type) {
                case 0: // 订阅事件
                    activeConsumers.add(event.consumerIdx);
                    break;
                case 1: // 取消订阅事件
                    activeConsumers.remove(event.consumerIdx);
                    break;
                case 2: // 消息事件
                    if (!activeConsumers.isEmpty()) {
                        int consumer = activeConsumers.first(); // 最高优先级的消费者
                        consumerMsgs.get(consumer).add(event.message);
                    }
                    break;
            }
        }

        // 输出结果
        for (List<Integer> msgs : consumerMsgs) {
            if (msgs.isEmpty()) {
                System.out.println(-1);
            } else {
                System.out.println(
                    String.join(" ", msgs.stream().map(String::valueOf).toArray(String[]::new))
                );
            }
        }
    }
}

代码解析

  1. Event 类：

    static class Event implements Comparable<Event> {
    int time;       // 事件时间
    int type;       // 0:订阅, 1:取消, 2:消息
    int consumerIdx; // 消费者索引
    int message;     // 消息内容
}
    • 封装事件的时间、类型、消费者索引和消息内容。

  2. 事件排序：

    @Override
public int compareTo(Event other) {
    if (this.time != other.time) return time比较结果;
    else return type比较结果; // 同一时间，订阅→取消→消息
}
    • 按时间升序排序，同一时间的事件按订阅 → 取消 → 消息的顺序处理。

  3. 解析输入：

    String[] msgInput = scanner.nextLine().split(" ");
for (int i = 0; i < msgInput.length; i += 2) {
    int time = Integer.parseInt(msgInput[i]);
    int msg = Integer.parseInt(msgInput[i + 1]);
    events.add(new Event(time, 2, -1, msg)); // 消息事件
}
    • 将输入拆分为消息时间和内容，生成消息事件。

  4. 处理消费者事件：

    String[] consumerInput = scanner.nextLine().split(" ");
for (int i = 0; i < m; i++) {
    int subTime = Integer.parseInt(consumerInput[2*i]);
    int unsubTime = Integer.parseInt(consumerInput[2*i+1]);
    events.add(new Event(subTime, 0, i, -1)); // 订阅事件
    events.add(new Event(unsubTime, 1, i, -1)); // 取消事件
}
    • 解析每个消费者的订阅和取消时间，生成对应事件。

  5. 维护活跃消费者：

    TreeSet<Integer> activeConsumers = new TreeSet<>(Collections.reverseOrder());
    • 使用 TreeSet 并按逆序排序，确保活跃消费者中优先级最高的（索引最大）排在前面。

  6. 处理消息事件：

    if (!activeConsumers.isEmpty()) {
    int consumer = activeConsumers.first(); // 最高优先级消费者
    consumerMsgs.get(consumer).add(event.message);
}
    • 当前有活跃消费者时，将消息发送给优先级最高的消费者。

示例测试

示例1：

输入：

2 22 1 11 4 44 5 55 3 33  
1 7 2 3

输出：

11 33 44 55  
22

解析：

  • 时刻1：消费者0订阅，发送消息11 → 消费者0接收。
  • 时刻2：消费者1订阅，发送消息22 → 消费者1接收。
  • 时刻3：消费者1取消，发送消息33 → 消费者0接收。
  • 时刻4和5：发送消息44和55 → 消费者0接收。
示例2：

输入：

5 64 11 64 9 97  
9 11 4 9

输出：

97  
64

解析：

  • 时刻5：消息64发送时只有消费者1活跃 → 消费者1接收。
  • 时刻9：消费者0订阅，消费者1取消，发送消息97 → 消费者0接收。

综合分析

  1. 时间复杂度：

    • 事件排序：O(E log E)，其中 E 是事件总数（消息 + 订阅 + 取消）。
    • 处理事件：O(E log M)，M 是消费者数量，TreeSet 操作复杂度为 O(log M)。
    • 总体复杂度 O(E log E + E log M)，满足题目要求。

  2. 空间复杂度：

    • 存储事件和消费者消息列表：O(E + M)，符合空间限制。

  3. 最优性：

    • 使用 TreeSet 高效维护活跃消费者，确保每次操作时间复杂度为 O(log M)。
    • 事件排序确保处理顺序符合题目要求，保证逻辑正确性。

  4. 适用性：

    • 处理大规模数据（消费者数 ≤ 1e4，消息数 ≤ 1e4）时依然高效。
    • 代码结构清晰，易于维护和扩展。

python

问题分析

我们需要模拟一个消息队列，其中包含发布者和多个消费者。发布者在特定时间发送消息，消费者在特定时间订阅或取消订阅。当消息发送时，如果有活跃的消费者，消息将发送给优先级最高的消费者（按输入顺序升序排列，后订阅的优先级更高）。输出每个消费者接收的消息，按接收顺序排列。

解决思路

  1. 事件收集与排序：将所有事件（订阅、取消、消息）按时间排序，同一时间的事件按订阅 → 取消 → 消息的顺序处理。
  2. 维护活跃消费者：使用集合保存当前活跃的消费者索引。
  3. 消息分发：处理消息时，选择优先级最高的活跃消费者（索引最大的消费者）。

Python 代码实现

def main():
    import sys

    # 读取输入
    msg_line = sys.stdin.readline().strip()
    consumer_line = sys.stdin.readline().strip()

    # 解析消息输入
    msg_parts = list(map(int, msg_line.split()))
    events = []
    for i in range(0, len(msg_parts), 2):
        time = msg_parts[i]
        content = msg_parts[i+1]
        events.append((time, 2, -1, content))  # 类型2表示消息

    # 解析消费者输入
    consumer_parts = list(map(int, consumer_line.split()))
    m = len(consumer_parts) // 2
    consumers = [[] for _ in range(m)]  # 存储每个消费者的消息
    for i in range(m):
        sub_time = consumer_parts[2*i]
        unsub_time = consumer_parts[2*i+1]
        events.append((sub_time, 0, i, -1))    # 类型0表示订阅
        events.append((unsub_time, 1, i, -1))  # 类型1表示取消

    # 排序事件：时间升序，同时间按类型升序（0 < 1 < 2）
    events.sort(key=lambda x: (x[0], x[1]))

    active_consumers = set()  # 当前活跃的消费者索引

    # 处理所有事件
    for event in events:
        time, typ, consumer_idx, content = event
        if typ == 0:  # 订阅
            active_consumers.add(consumer_idx)
        elif typ == 1:  # 取消
            if consumer_idx in active_consumers:
                active_consumers.remove(consumer_idx)
        elif typ == 2:  # 消息
            if active_consumers:
                # 选择优先级最高的消费者（索引最大的）
                max_consumer = max(active_consumers)
                consumers[max_consumer].append(content)

    # 输出结果
    for msgs in consumers:
        if not msgs:
            print(-1)
        else:
            print(" ".join(map(str, msgs)))

if __name__ == "__main__":
    main()

代码解析

  1. 输入解析：

    msg_parts = list(map(int, msg_line.split()))
for i in range(0, len(msg_parts), 2):
    events.append((time, 2, -1, content))
    • 将消息时间和内容解析为事件，类型为2（消息事件）。

  2. 消费者事件处理：

    for i in range(m):
    sub_time = consumer_parts[2*i]
    events.append((sub_time, 0, i, -1))  # 订阅事件
    events.append((unsub_time, 1, i, -1))  # 取消事件
    • 解析每个消费者的订阅和取消时间，生成对应事件。

  3. 事件排序：

    events.sort(key=lambda x: (x[0], x[1]))
    • 按时间升序排序，同一时间的事件按类型排序（订阅→取消→消息）。

  4. 维护活跃消费者：

    active_consumers = set()
if typ == 0:
    active_consumers.add(consumer_idx)
elif typ == 1:
    active_consumers.discard(consumer_idx)
    • 订阅时添加消费者索引，取消时移除。

  5. 消息分发：

    if active_consumers:
    max_consumer = max(active_consumers)
    consumers[max_consumer].append(content)
    • 当前有活跃消费者时，选择索引最大的（优先级最高）接收消息。

示例测试

示例1：

输入：

2 22 1 11 4 44 5 55 3 33  
1 7 2 3

输出：

11 33 44 55  
22

解析：

  • 时间1：消费者0订阅，发送消息11 → 消费者0接收。
  • 时间2：消费者1订阅，发送消息22 → 消费者1接收。
  • 时间3：消费者1取消，发送消息33 → 消费者0接收。
  • 时间4和5：发送消息44和55 → 消费者0接收。
示例2：

输入：

5 64 11 64 9 97  
9 11 4 9

输出：

97  
64

解析：

  • 时间5：消息64发送时只有消费者1活跃 → 消费者1接收。
  • 时间9：消费者0订阅，消费者1取消，发送消息97 → 消费者0接收。

综合分析

  1. 时间复杂度：

    • 事件排序：O(E log E)，E 是事件总数（消息 + 订阅 + 取消）。
    • 处理事件：O(E)，每次操作集合的时间复杂度为平均 O(1)。
    • 总体复杂度 O(E log E)，满足题目要求。

  2. 空间复杂度：

    • 存储事件和消费者消息列表：O(E + M)，符合空间限制。

  3. 正确性保障：

    • 事件排序确保处理顺序符合题目要求。
    • 使用集合维护活跃消费者，快速找到优先级最高的消费者。

  4. 优势：

    • 代码简洁，逻辑清晰。
    • 使用集合高效处理消费者状态的增删。
    • 严格按题目要求处理事件顺序。

JavaScript

问题分析

我们需要模拟一个消息队列系统，其中包含消息发布者和多个消费者。核心要求如下：

  1. 事件触发规则：

    • 发布者在特定时刻发送消息
    • 消费者在特定时刻订阅或取消订阅
    • 同一时刻的事件处理顺序：订阅 > 取消订阅 > 消息发送

  2. 消息分发规则：

    • 消息发送时，如果存在活跃消费者，发送给优先级最高的消费者（最后订阅的）
    • 没有消费者时消息丢弃

  3. 输出要求：

    • 每个消费者收到的消息按接收顺序排列
    • 未收到消息时输出 -1

解决思路

  1. 统一事件处理：

    • 将所有操作抽象为事件（订阅、取消订阅、消息）
    • 收集所有事件到同一队列

  2. 事件排序：

    • 按时间升序排列
    • 同一时间的事件按类型排序（订阅→取消→消息）

  3. 消费者管理：

    • 使用数组维护活跃消费者列表
    • 订阅时加入列表末尾（保证最后订阅的优先级最高）
    • 取消订阅时从列表中移除

  4. 消息分发：

    • 处理消息事件时，选择优先级最高的消费者（列表最后一个）

JavaScript 代码实现

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let inputLines = [];
rl.on('line', (line) => {
  inputLines.push(line.trim());
  if (inputLines.length === 2) processInput();
});

function processInput() {
  // ================= 输入解析阶段 =================
  // 解析消息数据（时间, 内容交替出现）
  const messageEvents = [];
  const msgParts = inputLines[0].split(' ').map(Number);
  for (let i = 0; i < msgParts.length; i += 2) {
    messageEvents.push({
      time: msgParts[i],
      type: 'MESSAGE', // 消息类型标识
      content: msgParts[i + 1]
    });
  }

  // 解析消费者数据（订阅时间, 取消时间交替出现）
  const consumerEvents = [];
  const consumerParts = inputLines[1].split(' ').map(Number);
  const consumers = Array.from({ length: consumerParts.length / 2 }, () => []);
  for (let i = 0; i < consumerParts.length; i += 2) {
    const subTime = consumerParts[i];
    const unsubTime = consumerParts[i + 1];
    
    // 添加订阅事件
    consumerEvents.push({
      time: subTime,
      type: 'SUBSCRIBE', // 订阅类型标识
      consumerIdx: i / 2 // 消费者索引
    });
    
    // 添加取消订阅事件
    consumerEvents.push({
      time: unsubTime,
      type: 'UNSUBSCRIBE', // 取消订阅类型标识
      consumerIdx: i / 2
    });
  }

  // ================= 事件处理阶段 =================
  // 合并所有事件并排序
  const allEvents = [...messageEvents, ...consumerEvents];
  
  // 自定义排序规则
  allEvents.sort((a, b) => {
    if (a.time !== b.time) {
      return a.time - b.time; // 时间升序
    }
    // 同一时间的事件类型优先级
    const typeOrder = { SUBSCRIBE: 0, UNSUBSCRIBE: 1, MESSAGE: 2 };
    return typeOrder[a.type] - typeOrder[b.type];
  });

  // 维护活跃消费者列表
  const activeConsumers = [];
  
  // 处理每个事件
  for (const event of allEvents) {
    switch (event.type) {
      case 'SUBSCRIBE':
        // 将消费者添加到列表末尾（保证最后订阅的优先级最高）
        activeConsumers.push(event.consumerIdx);
        break;
      
      case 'UNSUBSCRIBE':
        // 从列表中移除消费者
        const index = activeConsumers.indexOf(event.consumerIdx);
        if (index !== -1) {
          activeConsumers.splice(index, 1);
        }
        break;
      
      case 'MESSAGE':
        // 分发消息给最高优先级消费者
        if (activeConsumers.length > 0) {
          const targetConsumer = activeConsumers[activeConsumers.length - 1];
          consumers[targetConsumer].push(event.content);
        }
        break;
    }
  }

  // ================= 结果输出阶段 =================
  consumers.forEach(consumer => {
    console.log(consumer.length > 0 ? consumer.join(' ') : '-1');
  });
}

代码解析

1. 输入解析
// 解析消息数据
const msgParts = inputLines[0].split(' ').map(Number);
for (let i = 0; i < msgParts.length; i += 2) {
  messageEvents.push({
    time: msgParts[i],
    type: 'MESSAGE',
    content: msgParts[i + 1]
  });
}

// 解析消费者数据
const consumerParts = inputLines[1].split(' ').map(Number);
const consumers = Array.from({ length: consumerParts.length / 2 }, () => []);
for (let i = 0; i < consumerParts.length; i += 2) {
  // 生成订阅和取消事件
}
  • 将原始输入转换为结构化事件对象
  • 每个消费者初始化一个空消息列表
2. 事件排序
allEvents.sort((a, b) => {
  if (a.time !== b.time) return a.time - b.time;
  const typeOrder = { SUBSCRIBE: 0, UNSUBSCRIBE: 1, MESSAGE: 2 };
  return typeOrder[a.type] - typeOrder[b.type];
});
  • 优先按时间升序排列
  • 同一时间的事件按类型优先级排序
3. 消费者管理
case 'SUBSCRIBE':
  activeConsumers.push(event.consumerIdx);
  break;

case 'UNSUBSCRIBE':
  const index = activeConsumers.indexOf(event.consumerIdx);
  if (index !== -1) {
    activeConsumers.splice(index, 1);
  }
  break;
  • 订阅时添加到数组末尾
  • 取消时查找并移除元素
4. 消息分发
case 'MESSAGE':
  if (activeConsumers.length > 0) {
    const targetConsumer = activeConsumers[activeConsumers.length - 1];
    consumers[targetConsumer].push(event.content);
  }
  break;
  • 选择数组最后一个元素（最后订阅的）
  • 将消息存入对应消费者的消息列表

测试用例

用例1：

输入：

2 22 1 11 4 44 5 55 3 33
1 7 2 3

输出：

11 33 44 55
22

流程说明：

  1. 时间1：消费者0订阅 → 处理消息11
  2. 时间2：消费者1订阅 → 处理消息22
  3. 时间3：消费者1取消 → 处理消息33（发给消费者0）
  4. 时间4和5：消息44和55发给消费者0
用例2：

输入：

5 64 11 64 9 97
9 11 4 9

输出：

97
64

综合分析

  1. 时间复杂度：

    • 事件排序：O(n log n)
    • 事件处理：O(n * m)（m为消费者数量）
    • 满足题目要求的性能指标

  2. 空间复杂度：

    • 存储事件和消费者消息列表：O(n + m)

  3. 关键优势：

    • 统一的事件处理模型
    • 清晰的优先级管理逻辑
    • 易于扩展的事件类型支持

C++

问题分析

我们需要模拟一个消息队列，其中发布者在不同时刻发送消息，消费者在特定时刻订阅或取消订阅。消息发送时，优先发送给当前活跃且优先级最高的消费者（后订阅的优先级更高）。输出每个消费者接收的消息列表。

解决思路

  1. 事件收集与排序：将所有事件（订阅、取消、消息）按时间排序，同一时间的事件按订阅 → 取消 → 消息的顺序处理。
  2. 维护活跃消费者：使用动态数组存储活跃消费者索引，后订阅的消费者优先级更高。
  3. 消息分发：处理消息时，选择优先级最高的活跃消费者（数组末尾的消费者）。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <iterator>

using namespace std;

// 定义事件结构体
struct Event {
    int time;        // 事件发生时间
    int type;        // 0:订阅 1:取消 2:消息
    int consumerIdx; // 消费者索引
    int message;     // 消息内容
    
    Event(int t, int ty, int ci, int m) 
        : time(t), type(ty), consumerIdx(ci), message(m) {}
};

// 事件排序比较函数
bool compareEvents(const Event& a, const Event& b) {
    if (a.time != b.time) {
        return a.time < b.time; // 时间升序
    } else {
        return a.type < b.type; // 同一时间按类型排序
    }
}

int main() {
    // 读取输入
    string msgLine, consumerLine;
    getline(cin, msgLine);
    getline(cin, consumerLine);
    
    vector<Event> events;
    
    // 解析消息输入
    istringstream msgStream(msgLine);
    vector<int> msgData;
    int num;
    while (msgStream >> num) {
        msgData.push_back(num);
    }
    for (size_t i = 0; i < msgData.size(); i += 2) {
        events.emplace_back(msgData[i], 2, -1, msgData[i+1]);
    }
    
    // 解析消费者输入
    istringstream consumerStream(consumerLine);
    vector<int> consumerData;
    while (consumerStream >> num) {
        consumerData.push_back(num);
    }
    int m = consumerData.size() / 2;
    vector<vector<int>> consumers(m); // 存储每个消费者的消息
    
    for (int i = 0; i < m; ++i) {
        int subTime = consumerData[2*i];
        int unsubTime = consumerData[2*i+1];
        events.emplace_back(subTime, 0, i, -1);   // 订阅事件
        events.emplace_back(unsubTime, 1, i, -1);  // 取消事件
    }
    
    // 对事件排序
    sort(events.begin(), events.end(), compareEvents);
    
    vector<int> activeConsumers; // 当前活跃的消费者索引
    
    // 处理所有事件
    for (const auto& event : events) {
        switch (event.type) {
            case 0: // 订阅
                activeConsumers.push_back(event.consumerIdx);
                break;
            case 1: { // 取消
                auto it = find(activeConsumers.begin(), 
                              activeConsumers.end(), 
                              event.consumerIdx);
                if (it != activeConsumers.end()) {
                    activeConsumers.erase(it);
                }
                break;
            }
            case 2: // 消息
                if (!activeConsumers.empty()) {
                    int highest = activeConsumers.back();
                    consumers[highest].push_back(event.message);
                }
                break;
        }
    }
    
    // 输出结果
    for (const auto& msgs : consumers) {
        if (msgs.empty()) {
            cout << "-1" << endl;
        } else {
            for (size_t i = 0; i < msgs.size(); ++i) {
                if (i > 0) cout << " ";
                cout << msgs[i];
            }
            cout << endl;
        }
    }
    
    return 0;
}

代码解析

  1. 事件结构体：

    struct Event {
    int time;        // 时间
    int type;        // 类型（0:订阅 1:取消 2:消息）
    int consumerIdx; // 消费者索引
    int message;     // 消息内容
};
    • 封装事件的时间、类型、消费者索引和消息内容。

  2. 输入解析：

    istringstream msgStream(msgLine); // 消息输入流
while (msgStream >> num) { ... }  // 读取消息数据
for (size_t i = 0; i < msgData.size(); i += 2) {
    events.emplace_back(msgData[i], 2, -1, msgData[i+1]); // 生成消息事件
}
    • 解析消息输入，每两个数字为一组（时间、内容）。

  3. 消费者事件处理：

    events.emplace_back(subTime, 0, i, -1); // 订阅事件
events.emplace_back(unsubTime, 1, i, -1); // 取消事件
    • 每个消费者生成订阅和取消事件。

  4. 事件排序：

    sort(events.begin(), events.end(), compareEvents);
    • 按时间升序排序，同一时间的事件按类型排序（订阅→取消→消息）。

  5. 维护活跃消费者：

    vector<int> activeConsumers; // 活跃消费者索引数组
case 0: 
    activeConsumers.push_back(event.consumerIdx); // 订阅
case 1: 
    auto it = find(...); // 取消订阅，从数组中删除
    • 订阅时将消费者索引加入数组末尾（优先级最高）。
    • 取消时线性查找并删除。

  6. 消息分发：

    int highest = activeConsumers.back(); // 取最后一个元素（优先级最高）
consumers[highest].push_back(event.message);
    • 消息发送给当前优先级最高的消费者。

示例测试

示例1：

输入：

2 22 1 11 4 44 5 55 3 33  
1 7 2 3

输出：

11 33 44 55
22

解析：

  • 时刻1：消费者0订阅，处理消息11 → 消费者0接收。
  • 时刻2：消费者1订阅，处理消息22 → 消费者1接收。
  • 时刻3：消费者1取消，处理消息33 → 消费者0接收。
  • 时刻4和5：处理消息44、55 → 消费者0接收。
示例2：

输入：

5 64 11 64 9 97  
9 11 4 9

输出：

97
64

解析：

  • 时刻5：消息64发送时消费者1活跃 → 消费者1接收。
  • 时刻9：消费者0订阅，消费者1取消 → 消息97由消费者0接收。

综合分析

  1. 时间复杂度：

    • 事件排序：O(E log E)，其中 E 是事件总数。
    • 事件处理：O(E * M)，M 是消费者数量（线性查找取消操作）。
    • 总体时间复杂度满足题目要求（E ≤ 20000，M ≤ 1000）。

  2. 空间复杂度：

    • 存储事件和消费者消息列表：O(E + M)，符合空间限制。

  3. 优势：

    • 严格按时间顺序处理事件，逻辑清晰。
    • 使用动态数组维护活跃消费者，高效处理优先级。
    • 代码结构简洁，易于维护和扩展。

C语言

问题分析

我们需要模拟消息队列的运作，其中发布者在特定时刻发送消息，消费者在特定时刻订阅或取消订阅。消息发送时，优先发送给最后订阅的消费者。同一时刻的事件处理顺序为：订阅 → 取消 → 消息。

解决思路

  1. 事件统一管理：将所有事件（订阅、取消、消息）统一存储并排序。
  2. 优先级处理：后订阅的消费者优先级更高，用动态数组维护活跃消费者列表。
  3. 动态内存管理：使用动态数组存储消费者的消息列表，避免内存浪费。

完整代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_EVENTS 20000
#define MAX_CONSUMERS 1000
#define INIT_CAPACITY 4

// 事件类型枚举
typedef enum { SUBSCRIBE, UNSUBSCRIBE, MESSAGE } EventType;

// 事件结构体
typedef struct {
    int time;
    EventType type;
    int consumer_idx;
    int message;
} Event;

// 消费者消息存储结构
typedef struct {
    int* messages;    // 动态数组存储消息
    int size;         // 当前消息数量
    int capacity;     // 数组容量
} Consumer;

/*----------------------------------------------
 *               核心函数实现
 *--------------------------------------------*/

// 事件排序比较函数
int compare_events(const void* a, const void* b) {
    Event* e1 = (Event*)a;
    Event* e2 = (Event*)b;
    if (e1->time != e2->time) {
        return e1->time - e2->time; // 时间升序
    }
    return (int)e1->type - (int)e2->type; // 订阅→取消→消息
}

// 处理事件并分发消息
void process_events(Event* events, int event_count, Consumer* consumers, int consumer_count) {
    int active_consumers[MAX_CONSUMERS]; // 活跃消费者数组
    int active_count = 0;

    for (int i = 0; i < event_count; ++i) {
        Event e = events[i];
        switch (e.type) {
            case SUBSCRIBE:
                // 添加到活跃列表末尾
                active_consumers[active_count++] = e.consumer_idx;
                break;
                
            case UNSUBSCRIBE:
                // 快速移除：用最后一个元素覆盖
                for (int j = 0; j < active_count; ++j) {
                    if (active_consumers[j] == e.consumer_idx) {
                        active_consumers[j] = active_consumers[active_count - 1];
                        active_count--;
                        break;
                    }
                }
                break;
                
            case MESSAGE:
                if (active_count > 0) {
                    int target = active_consumers[active_count - 1];
                    Consumer* c = &consumers[target];
                    
                    // 动态扩容
                    if (c->size >= c->capacity) {
                        int new_cap = c->capacity == 0 ? INIT_CAPACITY : c->capacity * 2;
                        int* new_messages = realloc(c->messages, new_cap * sizeof(int));
                        if (new_messages) {
                            c->messages = new_messages;
                            c->capacity = new_cap;
                        }
                    }
                    c->messages[c->size++] = e.message;
                }
                break;
        }
    }
}

/*----------------------------------------------
 *               输入输出处理
 *--------------------------------------------*/

// 解析字符串到整数数组
int parse_numbers(char* str, int** result) {
    char* token = strtok(str, " ");
    int count = 0;
    int* arr = NULL;
    
    while (token != NULL) {
        arr = realloc(arr, (count + 1) * sizeof(int));
        arr[count++] = atoi(token);
        token = strtok(NULL, " ");
    }
    
    *result = arr;
    return count;
}

// 打印消费者消息
void print_consumers(Consumer* consumers, int count) {
    for (int i = 0; i < count; ++i) {
        if (consumers[i].size == 0) {
            printf("-1\n");
        } else {
            for (int j = 0; j < consumers[i].size; ++j) {
                if (j > 0) printf(" ");
                printf("%d", consumers[i].messages[j]);
            }
            printf("\n");
        }
    }
}

int main() {
    // 读取输入
    char msg_input[4096], consumer_input[4096];
    fgets(msg_input, sizeof(msg_input), stdin);
    fgets(consumer_input, sizeof(consumer_input), stdin);
    msg_input[strcspn(msg_input, "\n")] = '\0';
    consumer_input[strcspn(consumer_input, "\n")] = '\0';

    // 解析消息数据
    int* msg_data = NULL;
    int msg_count = parse_numbers(msg_input, &msg_data);
    int message_events = msg_count / 2;
    
    Event* events = malloc(MAX_EVENTS * sizeof(Event));
    int event_count = 0;
    
    for (int i = 0; i < message_events; ++i) {
        events[event_count++] = (Event){
            .time = msg_data[2*i], .type = MESSAGE,
            .consumer_idx = -1, .message = msg_data[2*i+1]
        };
    }
    free(msg_data);

    // 解析消费者数据
    int* consumer_data = NULL;
    int consumer_total = parse_numbers(consumer_input, &consumer_data);
    int consumer_count = consumer_total / 2;
    
    Consumer consumers[MAX_CONSUMERS] = {0};
    for (int i = 0; i < consumer_count; ++i) {
        events[event_count++] = (Event){
            .time = consumer_data[2*i], .type = SUBSCRIBE,
            .consumer_idx = i
        };
        events[event_count++] = (Event){
            .time = consumer_data[2*i+1], .type = UNSUBSCRIBE,
            .consumer_idx = i
        };
    }
    free(consumer_data);

    // 排序并处理事件
    qsort(events, event_count, sizeof(Event), compare_events);
    process_events(events, event_count, consumers, consumer_count);
    
    // 输出结果并清理内存
    print_consumers(consumers, consumer_count);
    for (int i = 0; i < consumer_count; ++i) {
        free(consumers[i].messages);
    }
    free(events);
    
    return 0;
}

代码解析

  1. 数据结构设计：

    • Event结构体：包含时间、类型、消费者索引和消息内容
    • Consumer结构体：动态数组存储消息，记录容量和当前大小

  2. 事件排序逻辑：

int compare_events(...) {
    if (e1->time != e2->time) return 时间差;
    return (int)e1->type - (int)e2->type; // SUBSCRIBE < UNSUBSCRIBE < MESSAGE
}
  1. 动态内存管理：
// 消费者消息数组扩容
if (c->size >= c->capacity) {
    int new_cap = c->capacity == 0 ? INIT_CAPACITY : c->capacity * 2;
    int* new_messages = realloc(c->messages, new_cap * sizeof(int));
}
  1. 高效取消订阅处理：
for (int j = 0; j < active_count; ++j) {
    if (active_consumers[j] == e.consumer_idx) {
        active_consumers[j] = active_consumers[active_count - 1];
        active_count--;
        break;
    }
}

测试用例

输入样例1：
2 22 1 11 4 44 5 55 3 33  
1 7 2 3
输出结果：
11 33 44 55
22
输入样例2：
5 64 11 64 9 97  
9 11 4 9
输出结果：
97
64

综合分析

  1. 时间复杂度：

    • 事件排序：O(n log n)
    • 事件处理：O(n * m)，m为消费者数
    • 满足题目数据规模要求

  2. 空间复杂度：

    • 存储事件和消费者消息：O(n + m)

  3. 关键优势：

    • 使用动态数组高效管理内存
    • 通过排序确保事件处理顺序正确
    • 清晰的代码结构便于维护

GO

问题分析

需要模拟消息队列的运作，其中包含发布者和多个消费者。核心要求：

  1. 事件顺序：订阅事件优先于取消事件，取消事件优先于消息事件。
  2. 消息分发：消息发送给最后订阅的消费者（优先级最高）。
  3. 输出：每个消费者收到的消息列表，若无消息则输出 -1。

解决思路

  1. 事件统一管理：将订阅、取消、消息事件统一存储，便于排序。
  2. 排序规则：先按时间升序，同一时间的事件按类型排序（订阅→取消→消息）。
  3. 维护活跃消费者：使用切片动态管理，后订阅的消费者优先级更高。
  4. 消息分发：处理消息事件时，选择活跃列表中最后一个消费者。

完整代码实现

package main

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
)

// 事件类型枚举
const (
	Subscribe   = 0
	Unsubscribe = 1
	Message     = 2
)

// Event 结构体
type Event struct {
	Time        int    // 事件时间
	Type        int    // 事件类型
	ConsumerIdx int    // 消费者索引（用于订阅/取消）
	Message     int    // 消息内容（仅消息事件）
}

func main() {
	// 读取输入
	var msgInput, consumerInput string
	fmt.Scanln(&msgInput)
	fmt.Scanln(&consumerInput)

	// 解析消息事件
	var events []Event
	msgParts := strings.Fields(msgInput)
	for i := 0; i < len(msgParts); i += 2 {
		time, _ := strconv.Atoi(msgParts[i])
		message, _ := strconv.Atoi(msgParts[i+1])
		events = append(events, Event{
			Time:    time,
			Type:    Message,
			Message: message,
		})
	}

	// 解析消费者事件
	consumerParts := strings.Fields(consumerInput)
	m := len(consumerParts) / 2
	consumers := make([][]int, m) // 每个消费者的消息列表

	for i := 0; i < m; i++ {
		subTime, _ := strconv.Atoi(consumerParts[2*i])
		unsubTime, _ := strconv.Atoi(consumerParts[2*i+1])
		// 添加订阅事件
		events = append(events, Event{
			Time:        subTime,
			Type:        Subscribe,
			ConsumerIdx: i,
		})
		// 添加取消事件
		events = append(events, Event{
			Time:        unsubTime,
			Type:        Unsubscribe,
			ConsumerIdx: i,
		})
	}

	// 事件排序：时间升序，同时间按类型排序
	sort.Slice(events, func(i, j int) bool {
		if events[i].Time != events[j].Time {
			return events[i].Time < events[j].Time
		}
		return events[i].Type < events[j].Type
	})

	// 维护活跃消费者列表
	activeConsumers := make([]int, 0)

	// 处理事件
	for _, event := range events {
		switch event.Type {
		case Subscribe:
			// 将消费者添加到列表末尾（后订阅的优先级更高）
			activeConsumers = append(activeConsumers, event.ConsumerIdx)
		case Unsubscribe:
			// 查找并移除消费者
			for idx, cIdx := range activeConsumers {
				if cIdx == event.ConsumerIdx {
					// 用最后一个元素覆盖并缩短切片
					activeConsumers[idx] = activeConsumers[len(activeConsumers)-1]
					activeConsumers = activeConsumers[:len(activeConsumers)-1]
					break
				}
			}
		case Message:
			if len(activeConsumers) > 0 {
				// 取优先级最高的消费者（最后订阅的）
				target := activeConsumers[len(activeConsumers)-1]
				consumers[target] = append(consumers[target], event.Message)
			}
		}
	}

	// 输出结果
	for _, msgs := range consumers {
		if len(msgs) == 0 {
			fmt.Println(-1)
		} else {
			fmt.Println(strings.Trim(fmt.Sprint(msgs), "[]"))
		}
	}
}

代码解析

  1. 事件结构体：统一管理事件的时间、类型、消费者索引和消息内容。
  2. 输入解析：
    • 消息事件：每两个数字为一组（时间、内容）。
    • 消费者事件：每两个数字为一组（订阅时间、取消时间）。
  3. 事件排序：按时间升序，同时间事件按类型排序（订阅→取消→消息）。
  4. 活跃消费者管理：
    • 订阅：将消费者索引添加到切片末尾。
    • 取消：查找索引并移除，优化为用末尾元素覆盖。
    • 消息分发：取切片最后一个消费者（优先级最高）。
  5. 输出处理：直接打印切片内容，使用 fmt.Sprint 转换为字符串并去除括号。

测试用例

输入1
2 22 1 11 4 44 5 55 3 33  
1 7 2 3
输出1
11 33 44 55
22
输入2
5 64 11 64 9 97  
9 11 4 9
输出2
97
64

综合分析

  1. 时间复杂度：
    • 事件排序：O(n log n)
    • 事件处理：O(n * m)（m 为消费者数量）
  2. 空间复杂度：存储事件和消费者消息列表，总体为 O(n + m)。
  3. 优势：
    • 利用 Go 切片特性高效管理动态数组。
    • 事件处理逻辑清晰，严格遵循时间顺序。
    • 代码简洁，易于维护和扩展。

更多内容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布