2.3 结构设计题-乱序接收顺序输出

🐌1. 题目描述

:::info

• 已知一个消息流会不断地吐出1-N，但不一定按照顺序吐出，如果上次打印的序号为i，那么当i+1出现时将打印i+1及其之后接收过的并且连续的所有数，直到1-N全部接收打印完成，请设计这种接收打印结构。

要求：接收N条数据，打印N条数据，包括内部调整的代价，整个过程保证时间复杂度为O(N) ::: 示例

// MessageBox only receive 1~N 
MessageBox box = new MessageBox(); 
// 1.... 
System.out.println("这是2来到的时候"); 
box.receive(2,"B"); // - 2" not print
System.out.println("这是1来到的时候"); 
box.receive(1,"A"); // 1 2 -> print, trigger is 1 
box.receive(4,"D"); // - 4 
box.receive(5,"E"); // - 4 5 
box.receive(7,"G"); // - 4 5 - 7 
box.receive(8,"H"); // - 4 5 - 7 8 
box.receive(6,"F"); // - 4 5 6 7 8 
box.receive(3,"C"); // 3 4 5 6 7 8 -> print, trigger is 3 
box.receive(9,"I"); // 9 -> print, trigger is 9 
box.receive(10,"J"); // 10 -> print, trigger is 10 
box.receive(12,"L"); // - 12 
box.receive(13,"M"); // - 12 13 
 box.receive(11,"K"); // 11 12 13 -> print, trigger is 11

💡2. 解决思路

使用简单结构单链表+Hash表拼凑出来这个乱序接收顺序打印结构

• 首先将需要打印的节点封装成单链表结构，这样接收到的非顺序到达的来连续节点可以连接起来。
• 然后准备两个HashMap,headMap,tailMap来分别存储已接收未打印的缓存链表的头尾节点信息。
• 最后一个变量waitPoint保存期待打印的序号信息。

时间复杂度分析：

• 接收调整过程中，节点查询，删除的使用由于使用的是HashMap，常数时间复杂度O(1)。
• 然后顺序打印，时间复杂度为O(N)。

额外空间复杂度分析：

• 申请的两个HashMap的大小。

算法流程描述：
（3，A），（5，C），（4，B）乱序到达，接收端接收之后，顺序输出（3，A），（4，B），（5，C）

1. （3，A）到达时，构建单链表节点，该节点头尾信息，都是3，分别存入到头表和尾表两个HashMap中，然后进行判断调整，看尾表中是否有2，如果有进行合并；看头表中是否有4，如果有进行合并。
2. （5，C）到达时，同上述操作，头表和尾表都无需调整。
3. （4，B）到达时，重复上述操作，进行判断调整，查找尾表中发现有3结尾的节点，进行3，4头尾合并，尾表中的3节点next指针指向4节点，则尾表中的3失效，头表中的4失效；继续查找是否有5开头的节点，进行4，5头尾合并，尾标中4节点的next指针指向5节点，则尾标中的4失效，头表中的5失效，调整完成之后该结构中剩下3开头的5结尾的一条单链表。如果此时期待打印的序号为3，则取出头节点进行顺序输出打印，打印完成之后将头尾失效节点移除。

🚩3. 代码实现

package class02;
import java.util.HashMap;

public class Code03_ReceiveAndPrintOrderLine {
    // 单链表结构
    public static class Node {
        public String info;
        public Node next;
        public Node(String str) {
            info = str;
        }
    }

    public static class MessageBox {
        private HashMap<Integer, Node> headMap;
        private HashMap<Integer, Node> tailMap;
        private int waitPoint;  // 等待要打印的序号

        public MessageBox() {
            headMap = new HashMap<Integer, Node>();
            tailMap = new HashMap<Integer, Node>();
            waitPoint = 1;
        }

        // 消息的编号，info消息的内容, 消息一定从1开始
        public void receive(int num, String info) {
            if (num < 1) {
                return;
            }
            Node cur = new Node(info);
            // num~num
            headMap.put(num, cur);
            tailMap.put(num, cur);
            // 建立了num~num这个连续区间的头和尾

            // 进行调整
            // 查询有没有某个连续区间以num-1结尾
            if (tailMap.containsKey(num - 1)) {
                tailMap.get(num - 1).next = cur;
                // 尾表num-1失效
                tailMap.remove(num - 1);
                // 头表num失效
                headMap.remove(num);
            }
            // 查询有没有某个连续区间以num+1开头的
            if (headMap.containsKey(num + 1)) {
                cur.next = headMap.get(num + 1);
                // 尾表num失效
                tailMap.remove(num);
                // 头表num+1失效
                headMap.remove(num + 1);
            }

            if (num == waitPoint) {
                print();
            }
        }

        // 打印
        private void print() {
            Node node = headMap.get(waitPoint);
            // 移除头表失效节点
            headMap.remove(waitPoint);
            while (node != null) {
                System.out.print(node.info + " ");
                node = node.next;
                waitPoint++;
            }
            // 移除尾表失效节点
            tailMap.remove(waitPoint-1);
            System.out.println();
        }

    }

    public static void main(String[] args) {
        // MessageBox only receive 1~N
        MessageBox box = new MessageBox();
        // 1....
        System.out.println("这是2来到的时候");
        box.receive(2,"B"); // - 2"
        System.out.println("这是1来到的时候");
        box.receive(1,"A"); // 1 2 -> print, trigger is 1
        box.receive(4,"D"); // - 4
        box.receive(5,"E"); // - 4 5
        box.receive(7,"G"); // - 4 5 - 7
        box.receive(8,"H"); // - 4 5 - 7 8
        box.receive(6,"F"); // - 4 5 6 7 8
        box.receive(3,"C"); // 3 4 5 6 7 8 -> print, trigger is 3
        box.receive(9,"I"); // 9 -> print, trigger is 9
        box.receive(10,"J"); // 10 -> print, trigger is 10
        box.receive(12,"L"); // - 12
        box.receive(13,"M"); // - 12 13
        box.receive(11,"K"); // 11 12 13 -> print, trigger is 11

    }
}

🔑4. 考点

单链表+HashMap